需要一种平面表示中数组索引的算法 [英] 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屋！
