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

Question

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

Ed.*_*Ed. 50 c++ oop hash maps data-structures

我正在研究一个需要操纵巨大矩阵的项目,特别是用于copula计算的金字塔总和.

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

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

速度是一个重中之重,我还想在运行时动态选择类中的变量数.

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

Answer 1

Mar*_*son 29

对于C++,地图效果很好.数百万个对象不会成为问题.在我的电脑上,1000万件物品花了大约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;
}

Run Code Online (Sandbox Code Playgroud)

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

Run Code Online (Sandbox Code Playgroud)

从中获取元素范围或检查范围是否完全在数组中的性能如何？ (2认同)
operator <的实现是不正确的.考虑Triple {1,2,3}和Triple {3,2,1},两者都不会小于另一个.正确的实现将检查x然后y然后z顺序而不是一次检查. (2认同)
由于没有修复很长时间，因此我自由地将其替换为正确的实现。 (2认同)
只有一百万元素的秒数？这似乎很糟糕.您应该考虑使用散列函数和`unordered_map`.查看https://github.com/victorprad/InfiniTAM他们使用散列`((x*73856093u)^(y*19349669u)^(z*83492791u))`并且可以将数百万个样本集成到稀疏的3D网格中良好的帧率. (2认同)

Answer 2

Kon*_*lph 19

作为一般建议,使用字符串作为索引的方法实际上非常慢.更有效但等效的解决方案是使用向量/数组.绝对没有必要在字符串中写索引.

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;

Run Code Online (Sandbox Code Playgroud)

然而,map由于在平衡二叉搜索树方面的实现,在实践中使用通常不是非常有效.在这种情况下,性能更好的数据结构将是哈希表,如提供的那样std::unordered_map.