需要一种平面表示中数组索引的算法 [英] Need of an algorithm for arrays index in a flat representation
问题描述
情况如下:我正在尝试实现一个适用于 N
维数组的解决方案,类似于下面的代码可以实现(还不是真正的编程语言):
The following is the situation: I am trying to implement a solution which works with N
dimensional arrays, something like the following code would make possible (not a real programming language yet):
int a[10,14,56]
将创建一个 3 维数组(即:一个 Cuboid),或者:
would create a 3 dimensional array (ie: a Cuboid), or:
int a[10,20]
显然会创建一个矩阵.
为了也能够表示数据,我决定为元素创建一个平面"内存区域.因此,对于 3 维向量,我分配 10 * 14 * 56
个整数,第二个我分配 10 * 20
个整数.
In order to be able to represent also the data, I have decided to create a "flat" memory area for the elements. So, for the 3 dimensional vector I allocate 10 * 14 * 56
ints and for the second I allocate 10 * 20
ints.
现在,问题来了:对于在给定索引处检索元素,对于一维数组和二维数组((i, j)
处的值,其中 i
计算行数,j
计算数组 N x M
中的列数,其中 N
是行数,M
是列数)我编写了公式:
Now, the problem comes: for retrieving an element at a given index the solution is self explaining for 1 dimensional arrays, and for the two dimensional arrays (value at (i, j)
where i
counts rows and j
counts columns in array N x M
where N
is row count and M
is column count) I cooked up the formula:
array[N, M] -> flat_memory [N * M]
flat_index(i,j) = M * i + j
对于我想出的 3 维数组:
and for the 3 dimensional arrays I came up with:
array[N, M, L] -> flat_memory[N * M * L]
flat_index(i, j, k) = L * i + M * j + k
但这感觉很糟糕......而且似乎我也无法进行概括:(所以在这里我转向社区:我的逻辑/计算中的缺陷是什么?是否有任何算法可以解决这个问题有什么问题吗?
but this feels bad ... and it seems I cannot get the step to the generalization either :( So here I turn to the community: What is the flaw in my logic/calculations? Are there any algorithms out there for this kind of problem?
推荐答案
我认为一个概括的方式如下
I think a generalization way as following
array[N, M, K] -> flat_memory[N * M * K]
array[N, M, K] -> flat_memory[N * M * K]
flat_index(i, j, k) = (M*N) * i + M * j + k
flat_index(i, j, k) = (M*N) * i + M * j + k
array[N, M, K, L] -> flat_memory[N * M * K * L]
array[N, M, K, L] -> flat_memory[N * M * K * L]
flat_index(i, j, k, l) = (M*N*K) * i + (M*N) * j + M* k + l
flat_index(i, j, k, l) = (M*N*K) * i + (M*N) * j + M* k + l
这篇关于需要一种平面表示中数组索引的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!