What is the best way to create a sparse array in C++? *

Question

I am working on a project that requires the manipulation of enourmous matrices, particularly 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 (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 am currently working on a system that uses a binary search tree (b-tree) to store entries. Does anyone know of a better system?

EDIT: Speed is a huge priority.

EDIT2 : 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]

Answer

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 {
        return (x < other.x && y < other.y && 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;
}

For multiple variables:

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;

< br > via < a class="StackLink" href=" http://stackoverflow.com/questions/4306/" >What is the best way to create a sparse array in C++?< /a>

Share on Google Plus

About Cinema Guy

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.