在C++中创建稀疏数组的最佳方法是什么？

Question

我正在做一个项目，它需要操作巨大的矩阵，特别是用于copula计算的金字塔求和。

简而言之，我需要跟踪矩阵(多维数组)中的大量零中相对较少的值(通常为1，在极少数情况下超过1)。

稀疏数组允许用户存储少量的值，并假定所有未定义的记录都是预设值。因为在物理上不可能在内存中存储所有的值，所以我只需要存储几个非零元素。这可能是几百万个条目。

速度是一个非常重要的因素，我还想在运行时动态选择类中的变量数量。

我目前在一个使用二叉树(b- tree )存储条目的系统上工作。有没有人知道更好的系统？

Answer 1

对于C++来说，地图工作得很好。几百万个对象不会成为问题。在我的电脑上，一千万个项目花了大约4.4秒和大约57兆。

我的测试应用程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <map>

class triple {
public:
    int x;
    int y;
    int z;
    bool operator<(const triple &other) const {
        if (x < other.x) return true;
        if (other.x < x) return false;
        if (y < other.y) return true;
        if (other.y < y) return false;
        return z < other.z;
    }
};

int main(int, char**)
{
    std::map<triple,int> data;
    triple point;
    int i;

    for (i = 0; i < 10000000; ++i) {
        point.x = rand();
        point.y = rand();
        point.z = rand();
        //printf("%d %d %d %d\n", i, point.x, point.y, point.z);
        data[point] = i;
    }
    return 0;
}

现在，要动态选择变量的数量，最简单的解决方案是将索引表示为字符串，然后使用字符串作为映射的键。例如，位于23处的项目可以通过"23,55“字符串表示。我们还可以将此解决方案扩展到更高的维度；例如，对于三维，任意索引将看起来像"34,45,56“。该技术的简单实现如下所示：

std::map data<string,int> data;
char ix[100];

sprintf(ix, "%d,%d", x, y); // 2 vars
data[ix] = i;

sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars
data[ix] = i;

Answer 2

公认的答案是建议使用字符串来表示多维索引。

然而，构造字符串是不必要的浪费。如果在编译时不知道大小(因此std::tuple无法工作)，std::vector可以很好地作为索引使用，可以使用散列映射和有序树。对于std::map来说，这几乎是微不足道的：

#include <vector>
#include <map>

using index_type = std::vector<int>;

template <typename T>
using sparse_array = std::map<index_type, T>;

对于std::unordered_map (或类似的基于哈希表的字典)，这项工作要稍微多一点，因为std::vector并不专门针对std::hash

#include <vector>
#include <unordered_map>
#include <numeric>

using index_type = std::vector<int>;

struct index_hash {
    std::size_t operator()(index_type const& i) const noexcept {
        // Like boost::hash_combine; there might be some caveats, see
        // <https://stackoverflow.com/a/50978188/1968>
        auto const hash_combine = [](auto seed, auto x) {
            return std::hash<int>()(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        };
        return std::accumulate(i.begin() + 1, i.end(), i[0], hash_combine);
    }
};

template <typename T>
using sparse_array = std::unordered_map<index_type, T, index_hash>;

无论哪种方式，用法都是相同的：

int main() {
    using i = index_type;

    auto x = sparse_array<int>();
    x[i{1, 2, 3}] = 42;
    x[i{4, 3, 2}] = 23;

    std::cout << x[i{1, 2, 3}] + x[i{4, 3, 2}] << '\n'; // 65
}

Answer 3

Boost有一个名为uBLAS的BLAS模板实现，其中包含一个稀疏矩阵。

https://www.boost.org/doc/libs/release/libs/numeric/ublas/doc/index.htm