在C ++中创建稀疏数组的最好方法是什么? [英] What is the best way to create a sparse array in C++?
问题描述
我正在开发一个需要处理巨大矩阵的项目,特别是用于copula计算的金字塔求和。
I am working on a project that requires the manipulation of enormous matrices, particularly pyramidal summation for a copula calculation.
简而言之,我需要在零海中记录相对较少的值(通常值为1,在极少数情况下超过1)在矩阵(多维数组)。
In short, I need to keep track of a relatively small number of values (usually a value of 1, and in rare cases more than 1) in a sea of zeros in the matrix (multidimensional array).
稀疏数组允许用户存储少量的值,并假定所有未定义的记录都是预设值。由于实际上不可能将所有值存储在内存中(数量大于Universe中的粒子数:p),因此我需要仅存储少数非零元素。这可能是几百万条目,我目前工作在使用二叉搜索树(b-tree)存储条目的系统。
A sparse array allows the user to store a small number of values, and assume all undefined records to be a preset value. Since it is not physically possibly to store all values in memory (greater in number than the number of particles in the universe :p ), I need to store only the few non-zero elements. This could be several million entries, I currently work on a system that uses a binary search tree (b-tree) to store entries.
有没有人知道更好的系统?
Does anyone know of a better system?
编辑:速度是一个巨大的优先级。
Speed is a huge priority.
编辑2:我喜欢这个解决方案。我将如何在运行时动态选择类中的变量数量?
EDIT 2 : I like that solution. How would I go about dynamically choosing the number of variables in the class at runtime? [edit by MH: good question, updated in the answer]
推荐答案
几百万个对象不会是一个问题。在我的电脑上有10万件物品耗时约4.4秒,约57百万块。
For C++, a map works well. Several million objects won't be a problem. 10 million items took about 4.4 seconds and about 57 meg on my computer.
#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,55(2 vars)或34,45,56(3 vars):
The easiest way is to make the index a string, and then make the index strings look like "23,55" (2 vars) or "34,45,56" (3 vars):
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 ++中创建稀疏数组的最好方法是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!