需要一个算法来处理以平面表示的数组索引问题

Question

以下是情况：我正在尝试实现一种可以使用N维数组的解决方案，类似下面的代码将会使其成为可能（并非真正的编程语言）：

int a[10,14,56]

会创建一个三维数组（即立方体）：或者：

int a[10,20]

显然会创建一个矩阵。

为了能够表示数据，我决定为元素创建一个“平坦”的内存区域。因此，对于三维向量，我分配了10 * 14 * 56个整数，对于第二个向量，我分配了10 * 20个整数。

现在，问题来了：对于给定索引的元素的检索，对于一维数组的解决方案是自解释的，对于二维数组（值为(i, j)，其中i计算行数，j计算列数，在数组N x M中，N是行数，M是列数），我想出了以下公式：

array[N, M] -> flat_memory [N * M]
flat_index(i,j) = M * i + j

就三维数组而言，我想到了以下方法：

array[N, M, L] -> flat_memory[N * M * L]
flat_index(i, j, k) = L * i + M * j + k

但是这感觉不太好……而且似乎我也无法进行归纳步骤:( 所以我向社区求助：我的逻辑/计算有什么缺陷？是否有任何算法可解决此类问题？

- Ferenc Deak

---

可能是setting-pointer-to-arbitrary-dimension-array的重复问题。 - Jarod42

Answer 1

试着写下一些带有所需索引的值。例如，对于 N = 1，M = 2，L = 3：

i  j  k  index
0  0  0  0
0  0  1  1
0  0  2  2
0  1  0  3
0  1  1  4
0  1  2  5
1  0  0  6
...

现在你只需要观察到每次增加 i，索引就应该增加 6，也就是 M*L。而每次增加 j，索引应该增加 3，也就是 L。

（更一般地说，你需要将某些维度的索引乘以所有低位维度的索引）

因此，我们有：

array[N, M, L] -> flat_memory[N * M * L]
flat_index(i, j, k) = M * L * i + L * j + k

这绝不是唯一可行的方法。您可以根据自己的需求重新安排顺序，适当更改乘数，因此以下都是有效的展平方法：

flat_index(i, j, k) = M * L * i + M * k + j

flat_index(i, j, k) = N * L * j + L * i + k
flat_index(i, j, k) = N * L * j + N * k + i

flat_index(i, j, k) = M * N * k + M * i + j
flat_index(i, j, k) = M * N * k + N * j + i

- Bernhard Barker

Answer 2

您可能对以下代码感兴趣，它可以让您使用任何“动态”尺寸：

#include <cassert>
#include <cstddef>

#include <vector>

template<typename T>
class MultiArray
{
public:
    explicit MultiArray(const std::vector<size_t>& dimensions) :
        dimensions(dimensions),
        values(computeTotalSize(dimensions))
    {
        assert(!dimensions.empty());
        assert(!values.empty());
    }

    const T& get(const std::vector<size_t>& indexes) const
    {
        return values[computeIndex(indexes)];
    }
    T& get(const std::vector<size_t>& indexes)
    {
        return values[computeIndex(indexes)];
    }

    size_t computeIndex(const std::vector<size_t>& indexes) const
    {
        assert(indexes.size() == dimensions.size());

        size_t index = 0;
        size_t mul = 1;

        for (size_t i = 0; i != dimensions.size(); ++i) {
            assert(indexes[i] < dimensions[i]);
            index += indexes[i] * mul;
            mul *= dimensions[i];
        }
        assert(index < values.size());
        return index;
    }

    std::vector<size_t> computeIndexes(size_t index) const
    {
        assert(index < values.size());

        std::vector<size_t> res(dimensions.size());

        size_t mul = values.size();
        for (size_t i = dimensions.size(); i != 0; --i) {
            mul /= dimensions[i - 1];
            res[i - 1] = index / mul;
            assert(res[i - 1] < dimensions[i - 1]);
            index -= res[i - 1] * mul;
        }
        return res;
    }

private:
    size_t computeTotalSize(const std::vector<size_t>& dimensions) const
    {
        size_t totalSize = 1;

        for (auto i : dimensions) {
            totalSize *= i;
        }
        return totalSize;
    }

private:
    std::vector<size_t> dimensions;
    std::vector<T> values;
};

让我们来测试一下：

int main()
{
    MultiArray<int> m({3, 2, 4});

    m.get({0, 0, 3}) = 42;
    m.get({2, 1, 3}) = 42;

    for (size_t i = 0; i != 24; ++i) {
        assert(m.computeIndex(m.computeIndexes(i)) == i);
    }
    return 0;
}

- Jarod42

Answer 3

我认为以下是一种通用的方式：

array[N, M, K] -> flat_memory[N * M * K]

flat_index(i, j, k) = (M*N) * i + M * j + k

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

- michaeltang

Answer 4

显然，对于一维数组，您只需要一个索引来访问所有元素：

array[N] -> flat_memory[N] <br />
flat_index(i) = i

如果您添加另一个维度，它变得如您所述正确：

array[N, M] -> flat_memory[N * M]<br />
flat_index(i, j) = M * i + j

第三个是：

和第三个：

array[N, M, K] -> flat_memory[N * M * L]<br />
flat_index(i, j, k) = (M * i + j) * N + k

我想现在你可以更清晰地看到模式了。对于每个新的维度，将上一个维度的大小乘以新的索引，并加上新的索引。

- B. M. Knecht