问题

我正在开发一个需要操作巨大矩阵的项目,特别是copula计算的金字塔总和.

简而言之,我需要在矩阵(多维数组)中零的海域中跟踪相对较少的数值(通常值为1,在罕见情况下超过1).

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

速度是一个巨大的优先级,我也想在运行时动态选择类中的变量数.

我目前正在研究一个使用二进制搜索树(b-tree)来存储条目的系统.有谁知道更好的系统吗?

  最佳答案

对于C,地图运行良好.数百万个对象不会成为问题.1000万个项目花费了大约4.4秒,大约57meg在我的计算机上.

我的测试应用程序如下:

 #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
", i, point.x, point.y, point.z);
        data[point] = i;
    }
    return 0;
}
 

现在动态选择变量数,最简单的解决方案是将索引表示为字符串,然后使用字符串作为映射的键.例如,位于[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;
 

  相同标签的其他问题

c++oopdata-structureshashmaps