在C ++中创建稀疏数组的最佳方式是什么？ [英] What is the best way to create a sparse array in C++?

问题描述

我正在研究一个需要操纵大量矩阵的项目，特别是Copula计算的金字塔求和。简而言之，我需要跟踪一个相对较少数量的值（通常值为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）返回true; 
 if（other.y< y）return false; 
返回z <其他
} 
}; 
 
 int main（int，char **）
 {
 std :: map< triple，int>数据; 
三点; 
 int i; （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>数据; 
 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; 
  

I am working on a project that requires the manipulation of enormous matrices, specifically pyramidal summation for a copula calculation.

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).

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, I need to store only the few non-zero elements. This could be several million entries.

Speed is a huge priority, and I would also like to dynamically choose the number of variables in the class at runtime.

I currently work on a system that uses a binary search tree (b-tree) to store entries. Does anyone know of a better system?

解决方案

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.

My test application is as follows:

#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;
}

Now to dynamically choose the number of variables, the easiest solution is to represent index as a string, and then use string as a key for the map. For instance, an item located at [23][55] can be represented via "23,55" string. We can also extend this solution for higher dimensions; such as for three dimensions an arbitrary index will look like "34,45,56". A simple implementation of this technique is as follows:

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屋！