4

这将是一个很长的问题，请在阅读之前深呼吸。

我想了解将一维数组的索引转换为多维数组的向量索引的最快算法是什么。

让我们通过一个例子来理解我为什么需要它：

我有一个二维数组： Array[i1][i2]

i1 从 i1_b=0 运行到 i1_e=2

i2 从 i2_b=0 运行到 i2_e=1

所以这个数组被逐行输出到文件中：

数组[0][0]

数组[0][1]

数组[0][2]

数组[1][0]

数组[1][1]

数组[1][2]

现在我逐行读取文件，索引 k 是最后读取的行号。

我读了第一行是 Array[0][0] 和 k=0

我读了第二行，即 Array[0][1] 和 k=1

...

可以注意到 k 将从 k_b=0 运行到 k_e=5 并且

k=0 将对应于 i1=0, i2=0

k=1 将对应于 i1=0, i2=1

...

问题：所以我的问题是如何以最快的方式将 k 转换为 i1 和 i2？（我在读取文件时不需要它，但稍后在我的程序中）

在此示例中，解决方案之一是

i1=k/(i1_e - i1_b + 1);

i2=k%(i1_e - i1_b + 1);

问题 1：就周期和计算机时间而言，这是最快的解决方案吗？

好的。问题 2：我们如何将这个算法推广到多维数组？

数组[i1][i2][i3][i4]

i1=k/(i1_e - i1_b + 1);

i2=k%(i1_e - i1_b + 1);

i3=i2/(i1_e - i1_b + 1);

i4=i2%(i1_e - i1_b + 1);

问题3：这是最快的方法吗？

问题 4：相关问题是模除法、整数除法、整数相加和整数相乘的延迟是多少？如果这些数字取决于架构，请告诉我。

提前致谢！

PS 有人可能更容易将此问题视为将秒转换为天-小时-分钟-秒的最快算法。

4

2 回答 2

7

问题 2：我们如何将这个算法推广到多维数组？

如果你有一个数组arr[dim_1][dim_2]...[dim_n]，你就有了等式

k = i_1*(dim_2*...*dim_n) + i_2*(dim_3*...*dim_n) + ... + i_{n-1}*dim_n + i_n
  = i_1*(dim_2*...*dim_n) + r_2

所以i_1 = k / (dim_2*..*dim_n)和r_2 = k % (dim_2*...*dim_n), 然后

i_2 = r_2 / (dim_3*...*dim_n) and r_3 = r_2 % (dim_3*...*dim_n)

ETC，

i_j = r_j / (dim_{j+1}*...*dim_n) and r_{j+1} = r_j % (dim_{j+1}*...*dim_n)

直到i_n = r_n被发现。

问题3：这是最快的方法吗？

如果在编译时已知维度，则可以用乘法、移位和加法/减法替换除法。在许多架构上，这比除法指令要快。在其他方面，不是。

但是，如果您在该数组中进行大量索引而不是其他任何事情，那么值得考虑一下。

问题 4：相关问题是模除法、整数除法、整数相加和整数相乘的延迟是多少？如果这些数字取决于架构，请告诉我。

这些数字取决于架构和处理器。

于 2012-07-20T21:17:38.167 回答
0

请在下面找到我将如何在 C++1x 中实现它，我希望这很有用。干杯

#include <iostream>
#include <array>
#include <algorithm>


/* stream arrays element by element to ostream */
template<size_t N, typename T>
std::ostream& operator<<(std::ostream& os, std::array<T, N> const&  obj)
{
  os << "{ ";
  for(auto a:obj)std::cout << a << " ";
  std::cout << "}";

  return os;
}

//end of recursion
template<size_t DIM, size_t I>
constexpr typename std::enable_if< (I==DIM), void  >::type
get_indexes(unsigned int index, std::array<unsigned int, DIM> const& depths, std::array<unsigned int,DIM>& indexes)
{}

//begin of the recursion
template<size_t DIM, size_t I=0>
constexpr typename std::enable_if< (I<DIM), void  >::type
get_indexes(unsigned int index, std::array<unsigned int, DIM> const& depths, std::array<unsigned int,DIM>& indexes)
{
    unsigned int  factor    =  1;
    for(unsigned int i=I+1; i<DIM; i++) factor *=depths[i];
    indexes[I]  =  index/factor;
    unsigned int next_index =  index%factor;
    get_indexes<DIM, I+1>(next_index, depths, indexes );
}

//some testing with 3 dimensions 
int main()
{
  constexpr unsigned ndimensions=3;
  std::array<unsigned int, ndimensions> depths{2, 3, 4};
  unsigned int nboxes = 1;

  for(unsigned int i =0; i< ndimensions; i++)nboxes *=depths[i];

  std::array<unsigned int, ndimensions> indexes;

  for(size_t i=0; i<nboxes; i++)
  {

    get_indexes<ndimensions>(i,depths ,  indexes);
    std::cout << i << " -> " <<indexes<< std::endl; 
  }


return 0;
}
于 2017-03-12T01:44:03.127 回答