这将是一个很长的问题,请在阅读之前深呼吸。
我想了解将一维数组的索引转换为多维数组的向量索引的最快算法是什么。
让我们继续看一个例子来理解为什么我需要它:
我有一个二维数组: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:相关问题是模除法、整数除法、整数加法和整数乘法的延迟是多少?如果这些数字取决于架构,也请告诉我。
提前致谢!
附:
有人可能更容易将此问题视为将秒转换为天-小时-分钟-秒的最快算法。
问题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
so i_1 = k / (dim_2*..*dim_n)
and r_2 = k % (dim_2*...*dim_n)
, then
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)
until i_n = r_n
被发现。
问题3:这是最快的方法吗?
如果维度在编译时已知,则可以用乘法、移位和加法/减法来代替除法。在许多体系结构上,这比除法指令更快。对其他人来说则不然。
但只有当你正在做一个事情时才值得考虑lot该数组中的索引,仅此而已。
问题4:相关问题是模除法、整数除法、整数加法和整数乘法的延迟是多少?如果这些数字取决于架构,也请告诉我。
这些数字取决于架构和处理器。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)