速度增益:将2D阵列转换为1D阵列

Question

我最初有一个2D数组。结果需要时间才能得到结果。所以，我将2D阵列转换为1D阵列，但程序的速度仍然没有太大的提高。

这是我的代码：

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个元素的2D数组生成的1D数组。NewSingleTable是由块大小为*（Total Next Elements）的2D数组生成的1D数组。

事实上，在转换成1D阵列后，我预计会有很大的速度增益。这是从1D数组中提取值的正确方法吗？还是可以对上述代码进行某些改进？

更多详细信息：

两个2D阵列都是结构类型：

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

Answer 1

您可以从向量的向量变为普通向量。例如：

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]...

这是因为向量中的一个向量并不是真正的矩阵，并且会失去数据的局部性。

更改自：

my_struct table[total_rows][total_columns];

至

my_struct table[total_rows * total_columns];

毫无价值，因为两者之间的内存布局（通常）完全相同。

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

当您必须对每个元素执行操作时，1D阵列可能会更快一些。这是因为循环更简单：

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在is comment中所说，复制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;
...