数组：将一维数组的索引转换为多维数组的向量索引

Question

这是一个比较长的问题，请先深呼吸再开始阅读。

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

我们来举个例子，以便理解为什么需要它：

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

i1从i1_b=0到i1_e=2运行，

i2从i2_b=0到i2_e=1运行，

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

Array[0][0]

Array[0][1]

Array[0][2]

Array[1][0]

Array[1][1]

Array[1][2]

现在我逐行读取文件，k是上次读取的行号。

可以注意到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：我们如何将该算法推广到多维数组？

Array[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：相关问题是模等分、整数除法、整数加法和整数乘法的延迟是多少？ 如果这些数字取决于架构，请也让我知道。

提前谢谢！

P.S. 对于某些人来说，将秒转换为天-小时-分钟-秒的最快算法可能更容易理解。

- user1541776

---

虽然真正的问题是，这会有影响吗？你进行了性能分析吗？ - orlp

@nightcracker：有时您的要求是尽可能快。并非所有代码都是简单的UI内容，小延迟并不意味着无关紧要。我偶尔会处理一些图像处理代码。目前它已经足够快以满足我们的要求。然而，如果/当我想到如何让它更快时，我会这样做，因为使这些算法更快会使我们的软件明显更快，进而使其更好。我并不是在说你错了，当然他应该进行性能分析。然而，对我来说，听起来OP正在寻求最快的解决方案，这是不同的。 - Ed S.

@nightcracker 在我的情况下，时间不是问题，但 EdS 理解了我的意思 - 我只想知道是否存在最快的解决方案，以在我未来的所有代码中使用。 - user1541776

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)

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

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

- Daniel Fischer

---

非常感谢您的回答！我只剩下一个问题：如果您提供的算法是回答第二个问题的最快方法吗？我很好奇，因为我猜所有程序员都需要“转换索引”，所以应该有“已知的最佳解决方案”或者至少调查一下这个“最佳解决方案”是否存在以及它取决于什么。 - user1541776

通常情况下，转换工作由编译器完成。对于访问arr[i1][i2][i3]这样的操作，会被转换为base_address + (i1*(d2*d3) + i2*d3 + i3)*sizeof(element_type)。如果维度在编译时已知，编译器应该能够找到最快的转换方式。无论是使用此形式并将常量d2*d3等作为编译时计算的文字插入，还是按照霍纳规则进行评估，都可能取决于具体情况，但没有根本上更快的方法。从偏移量到索引元组的转换要少得多，我不知道比除法更快的方法... - Daniel Fischer

但是在我熟悉的硬件上，如果维度是静态已知的话，将除法转换为移位、乘法和加法会更快。当然，如果所有维度都是2的幂，那就是最佳情况，只需要移位和掩码。 - Daniel Fischer

非常感谢您的帮助，您提供的详尽清晰的答案非常有帮助！ - user1541776

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;
}

- Antonio Augusto Alves Junior