array：将一维数组的索引转换为多维数组的向量索引 [英] array: convert index of one dimensional array to a vector index of a multidimensional array

问题描述

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

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

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

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

i1从i1_b = 0到i1_e = / p>

i2从i2_b = 0运行到i2_e = 1

按行输出到文件行：

Array [0] [0]

Array [0] [1]

Array [0] [2]

] [0]

数组[1] [1] p>

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

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

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

...

可以注意到k将从k_b = 0到k_e = 5和

运行。b $ b

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

k = 1将对应于i1 = 0，i2 = 1 问题：所以我的问题是如何将k转换成i1和i2的最快的速度。b / b

...

方式可能？
（我在阅读文件时不需要它，但稍后在我的程序中）

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

i1 = k /（i1_e - i1_b + 1）;

i2 = k％ （i1_e - i1_b + 1）;

问题1：这是循环周期和计算时间的最快解决方案吗？ p>

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

Array [i1] [i2] [i3] [ i4]

i1 = k /（i1_e - i1_b + 1）;

i2 = k％ - i1_b + 1）;

i3 = i2 /（i1_e-i1_b + 1）问题3：这是最快的方式吗？

$ i = 1％（i1_e - i1_b + 1）;

< b
$ b

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

$ c> 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）和r_ {j + 1} = r_j％（dim_ {j + 1} * ... * dim_n） b $ b  

，直到找到 i_n = r_n 问题3：这是最快的方法吗？

如果在编译时已知维度，则可以通过乘法，移位和加法/减法来替换除法。在许多架构上，这比分割指令快。在其他人，不是。

但是，唯一值得考虑的是，如果你在该数组中执行很多索引，而不是其他。

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

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

It will be a long question, please, take a deep breath before reading.

I want to understand what would be the fastest algorithm to convert index of one dimensional array to a vector index of a multidimensional array.

Let's proceed with an example to understand why do I need it:

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

So this array is outputted into the file line by line:

Array[0][0]

Array[0][1]

Array[0][2]

Array[1][0]

Array[1][1]

Array[1][2]

Now I read the file line by line and index k is the number of the line being read last.

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

...

One can notice that k will run from k_b=0 to k_e=5 and

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

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

...

Problem: So my problem is how to convert k into i1 and i2 the fastest way possible? (I don't need it while reading the file, but later in my program)

In this example, one of the solutions would be

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

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

Question 1: Is it the fastest possible solution in term of cycles and computer time?

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

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

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.

Thanks in advance!

P.S. It may be easier for someone to think about this problem as the fastest algorithm to convert seconds into days-hours-minutes-seconds.

解决方案

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

If you have an array arr[dim_1][dim_2]...[dim_n], you have the equation

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 is found.

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

If the dimensions are known at compile time, the divisions can be replaced by multiplications, shifts and additions/subtractions. On many architectures, that is faster than a division instruction. On others, not.

But it's only worthwhile thinking about if you're doing a lot of indexing in that array and not much else.

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.

These numbers depend on the architecture and processor.

这篇关于array：将一维数组的索引转换为多维数组的向量索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！