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

问题描述

这将是一个长期的问题，请深吸一口气看完了。

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

让我们用一个例子来进行理解，为什么我需要它：

  

我有一个二维数组：数组[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] [0-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）;

问题三：是不是这样做的最快方法

？

问题4：相关的问题是什么是模块化的分工，整数除法的延迟，增加整数和乘以整数？如果这些数字取决于架构，请，也让我知道了。

在此先感谢！

P.S。
它可能会更容易有人来思考这个问题，因为最快的算法，以秒转换为天，小时，分钟，秒。

解决方案

  

问题2：我们怎样才能推广这个算法多维数组

如果您有一个数组改编[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）和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）
 

直到 i_n = r_n 中找到。

  

问题三：是不是这样做的最快方法

？

如果尺寸是在编译时已知，这些部门可以通过乘法，移位和加法/减法来代替。在许多结构中，比一个除法指令更快。对他人，不能。

但它只有大约如果你正在做索引的许多该数组中，并没有多少人值得思考。

  

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

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