数组：转换成一维数组的索引多维数组的矢量指数

问题描述

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

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

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

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

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

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

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

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?

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.

解决方案

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.

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.

These numbers depend on the architecture and processor.

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