c++ - 速度增益 : Converting 2D array to 1D array

Question

我最初有一个二维数组。结果需要时间才能取回结果。因此，我将二维数组转换为一维数组，但我的程序速度仍然没有太大提高。

这是我的代码:

for( counter1=0; counter1< size ; ++counter1)
    {   
       y=buffer[counter1];
       x=buffer[counter1+1];

       IndexEntries index= OneDTable[x*256+y];

    SingleTableEntries NewNextState=NewSingleTable[Next*blocksize+index];

    Next=NewNextState.Next_State;
    if(NewNextState.accept[index.serialnumber]=='1' )
    {
        return 1;           
    }

在我上面的代码中:OneDTable 是从 256 * 256 元素的二维数组生成的一维数组。NewSingleTable 是一个一维数组，由 block 大小*(下一个元素总数)的二维数组生成。

实际上，我期望转换为一维数组后速度会大幅提升。这是从一维数组中提取值的正确方法还是可以对上述代码进行某些改进？

更多详情:

两个二维数组都是结构类型:

Structure type of IndexEntries consists of:
          int  
          int

Structure type of NewSingleTable consists of:
          int
          vector<char>

Answer 1

您可以获得从 vector 的 vector 到普通 vector 的变化。例如。来自:

std::vector<std::vector<my_struct>> table(total_rows,
                                          std::vector<my_struct>(total_columns,
                                                                 my_struct()));

// do something with table[row][column]...

到

std::vector<my_struct> table(total_rows * total_columns);

// do something with table[row * total_columns + column]...

这是因为 vector of vector is not really a matrix and you lose data locality .

改变自:

my_struct table[total_rows][total_columns];

到

my_struct table[total_rows * total_columns];

毫无值(value)，因为两者之间的内存布局(通常)完全相同。

唯一的区别是数组的语义类型以及您现在必须自己实现 2D 元素查找的事实(当然，从 table[row * 256 + column] 更改为 table[row << 8 + column] 是无用的，因为任何像样的编译器都会自动执行此操作“优化”)。

当您必须对每个元素执行操作时，一维数组可能会更快一些。这是因为更简单的 for 循环:

for (unsigned row(0); row < total_rows; ++row)
  for (unsigned column(0); column < total_columns; ++column)
    // do something with table[row][column]

const unsigned stop(total_rows * total_columns);
for (unsigned i(0); i < stop; ++i)
  // do something with table[i]

但这不是你的情况。

正如 laune 在评论中所说，复制 NewSingleTable 只是为了提取几个整数是不好的:

SingleTableEntries NewNextState=NewSingleTable[Next*blocksize+index];

从你的例子来看，const 引用似乎就足够了:

...
const SingleTableEntries &NewNextState(NewSingleTable[Next * blocksize + index]);

if (NewNextState.accept[index.serialnumber] == '1' )
  return 1;           

Next = NewNextState.Next_State;
...