平面表示中数组索引算法的需要

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

但这感觉不好..。而且，我似乎也无法进行概括:(因此，我现在转向社区:我的逻辑/计算中有什么缺陷？)对于这类问题有什么算法吗？

Answer 1

我认为一个概括的方法如下

arrayN，M，K -> flat_memoryN *M*K

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

arrayN，M，K，L -> flat_memoryN *M*K*L

flat_index(i，j，k，l) = ( M* N*K) *i+ (M*N) *j+M*k+l

Answer 2

尝试用所需的索引写下几个值。因此，对于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

Answer 3

您可能对允许使用任何“动态”维度的下列代码感兴趣：

#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;
}