Quelle est la meilleure façon de créer un tableau fragmenté en C ++?

Question

Je suis en train de travailler sur un projet qui nécessite la manipulation d'énormes matrices, en particulier pyramidale de sommation pour une copule de calcul. En bref, j'ai besoin de garder une trace d'un relativement petit nombre de valeurs (généralement, une valeur de 1, et dans de rares cas, plus de 1) dans une mer de zéros dans la matrice (tableau multidimensionnel). Un tableau fragmenté permet à l'utilisateur de conserver un petit nombre de valeurs, et d'assumer tous les indéfini enregistrements à une valeur prédéfinie. Car il n'est pas physiquement éventuellement de stocker toutes les valeurs en mémoire (plus nombreux que le nombre de particules dans l'univers :p ), j'ai besoin de stocker uniquement les quelques non-zéro éléments. Cela pourrait être de plusieurs millions d'entrées. Je suis actuellement en train de travailler sur un système qui utilise un arbre de recherche binaire (b-tree) pour stocker les entrées. Personne ne sait d'un meilleur système?

EDIT: la Vitesse est une priorité.

EDIT2 : j'aime bien cette solution. Comment puis-je choisir dynamiquement le nombre de variables dans la classe au moment de l'exécution? [edit par MH: bonne question, mis à jour dans la réponse]

Answer 1

Pour C ++, une carte fonctionne bien. Plusieurs millions d'objets ne seront pas un problème. 10 millions d'articles ont pris environ 4,4 secondes et environ 57 mégaoctets sur mon ordinateur.

 #include <stdio.h> 

Pour plusieurs variables:

Le moyen le plus simple consiste à faire de l'index une chaîne, puis à faire en sorte que les chaînes d'index ressemblent à "23,55" (2 vars) ou "34,45,56" (3 vars):

Answer 2

Tout comme un conseiller: la méthode à l'aide de chaînes de caractères comme des indices est effectivement très lent. Beaucoup plus efficace, mais autrement équivalent solution serait d'utiliser des vecteurs/matrices. Il n'y a absolument pas besoin d'écrire les indices dans une chaîne de caractères.

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;

Cependant, à l'aide d'un map n'est en fait pas très efficace en raison de la mise en œuvre en termes d'équilibre binaire un arbre de recherche. Beaucoup plus performante que les structures de données dans ce cas serait un (aléatoires) de la table de hachage.

Answer 3

Boost a une implémentation modèle de BLAS appelée uBLAS qui contient une matrice clairsemée.

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm

Answer 4

Vous souhaitez SparseLib++ (http://math.nist.gov/sparselib++/) ou Pardiso(http://www.pardiso-project.org/manual/index.html). Pardiso est C de sorte que vous aurez à créer certains wrapper C++ code. Haute performance matrice bibliothèques sont une de ces choses qui semblent simples à mettre en œuvre mais ne le sont pas, il est donc préférable d'aller avec quelque chose de créé par des équipes de scientifiques. Aussi, regardez dans la colonne "stockage compressé"(à l'aide de tableaux) pour l'un des moyens les plus efficaces pour stocker de grandes matrices en mémoire.

Answer 5

Petit détail dans la comparaison d'index. Vous devez faire une comparaison lexicographique, sinon:

 a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a
 

Edit: Donc, la comparaison devrait probablement être:

 return lhs.x<rhs.x
    ? true 
    : lhs.x==rhs.x 
        ? lhs.y<rhs.y 
            ? true 
            : lhs.y==rhs.y
                ? lhs.z<rhs.z
                : false
        : false