阵列：转换一个维阵列的索引到一个多维阵列的向量索引(array: convert index of

这将是一个长期的问题，请深呼吸读数。

我想知道什么是最快的算法，以一个维数组的索引转换为一个多维数组的矢量指数。

让我们用一个例子继续理解为什么需要它：

我有一个2维数组：数组[I1] [12]
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是被最后读取的行数。

我读取的第一线，其是阵列[0] [0]，且k = 0
我读取第二线，其是阵列[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] [12] [i3的] [6-14]
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有人来思考这个问题，因为最快的算法，以秒转换为天，小时 - 分 - 秒，它可能会更容易。

Answer 1:

问题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)

等等，

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：相关的问题是什么是模块化划分，整数除法的等待时间，增加整数和乘以整数？如果这些数字取决于架构，请，也让我知道。

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

Answer 2:

请看下面我将如何实现这个在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;
}

文章来源: array: convert index of one dimensional array to a vector index of a multidimensional array