我正在做一个需要处理大量矩阵的项目，特别是用于求模算的金字塔式求和。

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

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

速度是重中之重，我还想在运行时动态选择类中的变量数量。

我目前正在使用二进制搜索树(b-tree)存储条目的系统上工作。有人知道更好的系统吗？

解决方案

回答

对于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;
}

现在要动态选择变量的数量，最简单的解决方案是将index表示为字符串，然后将string用作映射的键​​。例如，可以通过" 23,55"字符串表示位于[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;

回答

哈希表具有快速插入和查找的功能。我们可以编写一个简单的哈希函数，因为我们知道只处理整数对作为键。

回答

实现稀疏矩阵的最佳方法是不要至少自己实现。我建议使用BLAS(我认为它是LAPACK的一部分)，它可以处理非常大的矩阵。

回答

索引比较中的小细节。我们需要进行字典比较，否则：

a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a

编辑：因此，比较可能应该是：

return lhs.x<rhs.x
    ? true 
    : lhs.x==rhs.x 
        ? lhs.y<rhs.y 
            ? true 
            : lhs.y==rhs.y
                ? lhs.z<rhs.z
                : false
        : false

回答

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

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm

回答

就像一个建议：使用字符串作为索引的方法实际上非常慢。一个更有效但在其他方面等效的解决方案是使用向量/数组。绝对没有必要在字符串中编写索引。

typedef vector<size_t> index_t;

struct index_cmp_t : binary_function<index_t, index_t, bool> {
    bool operator ()(index_t const& a, index_t const& b) const {
        for (index_t::size_type i = 0; i < a.size(); ++i)
            if (a[i] != b[i])
                return a[i] < b[i];
        return false;
    }
};

map<index_t, int, index_cmp_t> data;
index_t i(dims);
i[0] = 1;
i[1] = 2;
// … etc.
data[i] = 42;

但是，使用" map"实际上并不是很有效，因为它是根据平衡的二进制搜索树实现的。在这种情况下，性能更好的数据结构是(随机)哈希表。

回答

由于仅具有[a] [b] [c] ... [w] [x] [y] [z]的值是重要的，因此我们仅存储索引本身，而不存储值1，因为值1总是随处可见。同样+没有办法对其进行哈希处理。注意存在维度的诅咒，建议使用一些已建立的工具NIST或者Boost，至少阅读其来源以规避不必要的错误。

如果工作需要捕获未知数据集的时间依赖性分布和参数趋势，则具有单值根的Map或者B-Tree可能不切实际。对于所有1个值，我们只能存储索引本身，如果排序(表示的敏感性)可以服从于运行时时域的减少，则可以对其进行散列处理。由于除了一个以外的非零值很少，因此可以很容易找到并理解的任何数据结构都是显而易见的选择。如果数据集确实是巨大的宇宙，我建议我们使用某种可自行管理文件/磁盘/持久性io的滑动窗口，并根据需要将部分数据移入范围。 (编写我们可以理解的代码)如果我们承诺为工作组提供实际的解决方案，那么如果我们不这样做，我们将只能依靠消费级操作系统，而这些操作系统的唯一目的是使午餐不再为时。