Les tables de hachage ont une insertion et une recherche rapides. Vous pouvez écrire une fonction de hachage simple puisque vous savez que vous n'aurez affaire qu'à des paires d'entiers comme clés.

La meilleure façon d'implémenter des matrices creuses est de ne pas les implémenter - du moins pas par vous-même. Je suggérerais à BLAS (qui, je pense, fait partie de LAPACK) qui peut gérer des matrices vraiment énormes.

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

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

Modifier : 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

Juste un conseil : la méthode utilisant des chaînes comme indices est en fait très lente. Une solution beaucoup plus efficace mais autrement équivalente serait d'utiliser des vecteurs/tableaux. Il n'est absolument pas nécessaire d'écrire les indices dans une chaîne.

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'utilisation d'un map n'est en fait pas très efficace en raison de l'implémentation en termes d'arbre de recherche binaire équilibré. Dans ce cas, des structures de données beaucoup plus performantes seraient une table de hachage (randomisée).

Puisque seules les valeurs avec [a][b][c]...[w][x][y][z] sont importantes, nous ne stockons que l'indice lui-même, pas la valeur 1 qui est à peu près partout - toujours le même aucun moyen de le hacher. Notant que la malédiction de la dimensionnalité est présente, suggérons d'aller avec un outil établi NIST ou Boost, lisez au moins les sources pour éviter les erreurs inutiles.

Si le travail doit capturer les distributions de dépendance temporelle et les tendances paramétriques d'ensembles de données inconnus, alors une carte ou un arbre B avec une racine à valeur unique n'est probablement pas pratique. Nous ne pouvons stocker que les indices eux-mêmes, hachés si l'ordre (sensibilité pour la présentation) peut être subordonné à la réduction du domaine temporel au moment de l'exécution, pour toutes les valeurs 1. Étant donné que les valeurs non nulles autres que un sont peu nombreuses, un candidat évident pour celles-ci est la structure de données que vous pouvez trouver facilement et comprendre. Si l'ensemble de données est vraiment de la taille d'un vaste univers, je suggère une sorte de fenêtre coulissante qui gère vous-même le fichier / disque / persistant-io, en déplaçant des parties des données dans la portée selon les besoins. (écrire du code que vous pouvez comprendre) Si vous vous engagez à fournir une solution réelle à un groupe de travail, ne pas le faire vous laisse à la merci des systèmes d'exploitation grand public qui ont pour seul objectif de vous prendre votre déjeuner.< /p>