c++ - 数组 : convert index of one dimensional array to a vector index of a multidimensional array

Question

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

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

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

I have a 2 dimensional array: Array[i1][i2]

i1 runs from i1_b=0 to i1_e=2

i2 runs from i2_b=0 to i2_e=1

所以这个数组是逐行输出到文件中的:

Array[0][0]

Array[0][1]

Array[0][2]

Array[1][0]

Array[1][1]

Array[1][2]

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

I read the first line which is Array[0][0] and k=0

I read the second line which is Array[0][1] and k=1

...

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

k=0 will correspond to i1=0, i2=0

k=1 will correspond to i1=0, i2=1

...

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

在这个例子中，其中一个解决方案是

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

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

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

好的。问题二:如何将这个算法推广到多维数组？

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

提前致谢!

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

Answer 1

Question 2: How can we generalize this algorithm to multidimensional arrays?

如果你有一个数组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。

Question 3: Is it the fastest way to do it?

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

但只有在该数组中进行大量索引而不是其他操作时才值得考虑。

Question 4: related question would be what is the latency for modular division, integer division, adding integers and multiplying integers? If these numbers depend on the architecture, please, also let me know.

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