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

Juste comme un conseil: la méthode utilisant des chaînes comme indices est en fait Très lente. Une solution beaucoup plus efficace mais sinon é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 pas vraiment très efficace en raison de l'implémentation en termes d'arbre de recherche binaire équilibré. Des structures de données beaucoup plus performantes dans ce cas seraient une table de hachage (randomisée).

Boost a une implémentation template 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

Petit détail dans la comparaison de l'indice. 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

Les tables de hachage ont une insertion rapide et recherchent. Vous pouvez écrire une fonction de hachage simple puisque vous savez que vous ne traiterez que des paires entières comme clés.

Eigen est une bibliothèque d'algèbre linéaire c++ qui a une implémentation d'une matrice clairsemée. Il prend même en charge les opérations matricielles et les solveurs (factorisation LU, etc.) optimisés pour les matrices clairsemées.

La liste complète des solutions peut être trouvée dans wikipedia. Pour plus de commodité, j'ai cité les sections pertinentes comme suit.

Https://en.wikipedia.org/wiki/Sparse_matrix#Dictionary_of_keys_.28DOK.29

Dictionnaire des clés (DOK)

DOK se compose d'un dictionnaire qui mappe (ligne, colonne)-paires au la valeur des éléments. Éléments manquants dans le dictionnaire sont considérées comme nulles. Le format est bon pour incrémental construire une matrice clairsemée dans un ordre aléatoire, mais pauvre pour l'itération sur des valeurs non nulles dans l'ordre lexicographique. Celle généralement construit une matrice dans ce format puis convertit en une autre plus format efficace pour le traitement.[1]

Liste des listes (LIL)

Lil stocke une liste par ligne, chaque entrée contenant la colonne l'index et la valeur. Généralement, ces entrées sont triées par index de colonne pour une recherche plus rapide. Ceci est un autre format bon pour construction de matrice incrémentale.[2]

Liste de coordonnées (COO)

COO stocke une liste de tuples (ligne, colonne, Valeur). Idéalement, les entrées sont triés (par index de ligne, puis un index de colonne) pour améliorer l'accès aléatoire temps. C'est un autre format qui est bon pour la matrice incrémentale construction.[3]

Ligne clairsemée compressée (format CSR, CRS ou Yale)

La ligne clairsemée compressée (CSR) ou le stockage de ligne compressée (CRS) format représente une matrice M par trois tableaux (unidimensionnels), qui contiennent respectivement des valeurs non nulles, l'étendue des lignes et la colonne index. Il est similaire à COO, mais compresse les indices de ligne, donc nom. Ce format permet un accès rapide à la ligne et à la matrice-vecteur multiplications (Mx).

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

Puisque seules les valeurs avec [a][b][c]...[w] [x] [y] [z] sont de conséquence, nous ne stockons que l'indice eux - mêmes, 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érez d'aller avec un outil établi NIST ou Boost, au moins lire les sources pour contourner la gaffe inutile.

Si le travail doit capturer les distributions de dépendance temporelle et les tendances paramétriques des ensembles de données inconnus, ensuite, une carte ou un arbre B avec une racine à valeur unique n'est probablement pas pratique. Nous ne pouvons stocker que l'indice eux-mêmes, haché si l'ordre (sensibilité pour la présentation) peut subordonner à la réduction du domaine temporel à l'exécution, pour toutes les 1 Valeurs. Puisque les valeurs non nulles autres qu'Une 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 vaste, je suggère une sorte de fenêtre coulissante qui gère le fichier / disque / persistant-io vous-même, déplaçant des parties des données dans la portée au besoin. (code d'écriture que vous pouvez comprendre ) si vous êtes sous l'engagement de fournir une solution réelle à un groupe de travail, ne pas le faire vous laisse à la merci des systèmes d'exploitation de qualité des consommateurs qui ont le seul but de prendre votre déjeuner loin de vous.

Voici une implémentation relativement simple qui devrait fournir une recherche rapide raisonnable (en utilisant une table de hachage) ainsi qu'une itération rapide sur des éléments non nuls dans une ligne/colonne.

// Copyright 2014 Leo Osvald
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef UTIL_IMMUTABLE_SPARSE_MATRIX_HPP_
#define UTIL_IMMUTABLE_SPARSE_MATRIX_HPP_

#include <algorithm>
#include <limits>
#include <map>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>

// A simple time-efficient implementation of an immutable sparse matrix
// Provides efficient iteration of non-zero elements by rows/cols,
// e.g. to iterate over a range [row_from, row_to) x [col_from, col_to):
//   for (int row = row_from; row < row_to; ++row) {
//     for (auto col_range = sm.nonzero_col_range(row, col_from, col_to);
//          col_range.first != col_range.second; ++col_range.first) {
//       int col = *col_range.first;
//       // use sm(row, col)
//       ...
//     }
template<typename T = double, class Coord = int>
class SparseMatrix {
  struct PointHasher;
  typedef std::map< Coord, std::vector<Coord> > NonZeroList;
  typedef std::pair<Coord, Coord> Point;

 public:
  typedef T ValueType;
  typedef Coord CoordType;
  typedef typename NonZeroList::mapped_type::const_iterator CoordIter;
  typedef std::pair<CoordIter, CoordIter> CoordIterRange;

  SparseMatrix() = default;

  // Reads a matrix stored in MatrixMarket-like format, i.e.:
  // <num_rows> <num_cols> <num_entries>
  // <row_1> <col_1> <val_1>
  // ...
  // Note: the header (lines starting with '%' are ignored).
  template<class InputStream, size_t max_line_length = 1024>
  void Init(InputStream& is) {
    rows_.clear(), cols_.clear();
    values_.clear();

    // skip the header (lines beginning with '%', if any)
    decltype(is.tellg()) offset = 0;
    for (char buf[max_line_length + 1];
         is.getline(buf, sizeof(buf)) && buf[0] == '%'; )
      offset = is.tellg();
    is.seekg(offset);

    size_t n;
    is >> row_count_ >> col_count_ >> n;
    values_.reserve(n);
    while (n--) {
      Coord row, col;
      typename std::remove_cv<T>::type val;
      is >> row >> col >> val;
      values_[Point(--row, --col)] = val;
      rows_[col].push_back(row);
      cols_[row].push_back(col);
    }
    SortAndShrink(rows_);
    SortAndShrink(cols_);
  }

  const T& operator()(const Coord& row, const Coord& col) const {
    static const T kZero = T();
    auto it = values_.find(Point(row, col));
    if (it != values_.end())
      return it->second;
    return kZero;
  }

  CoordIterRange
  nonzero_col_range(Coord row, Coord col_from, Coord col_to) const {
    CoordIterRange r;
    GetRange(cols_, row, col_from, col_to, &r);
    return r;
  }

  CoordIterRange
  nonzero_row_range(Coord col, Coord row_from, Coord row_to) const {
    CoordIterRange r;
    GetRange(rows_, col, row_from, row_to, &r);
    return r;
  }

  Coord row_count() const { return row_count_; }
  Coord col_count() const { return col_count_; }
  size_t nonzero_count() const { return values_.size(); }
  size_t element_count() const { return size_t(row_count_) * col_count_; }

 private:
  typedef std::unordered_map<Point,
                             typename std::remove_cv<T>::type,
                             PointHasher> ValueMap;

  struct PointHasher {
    size_t operator()(const Point& p) const {
      return p.first << (std::numeric_limits<Coord>::digits >> 1) ^ p.second;
    }
  };

  static void SortAndShrink(NonZeroList& list) {
    for (auto& it : list) {
      auto& indices = it.second;
      indices.shrink_to_fit();
      std::sort(indices.begin(), indices.end());
    }

    // insert a sentinel vector to handle the case of all zeroes
    if (list.empty())
      list.emplace(Coord(), std::vector<Coord>(Coord()));
  }

  static void GetRange(const NonZeroList& list, Coord i, Coord from, Coord to,
                       CoordIterRange* r) {
    auto lr = list.equal_range(i);
    if (lr.first == lr.second) {
      r->first = r->second = list.begin()->second.end();
      return;
    }

    auto begin = lr.first->second.begin(), end = lr.first->second.end();
    r->first = lower_bound(begin, end, from);
    r->second = lower_bound(r->first, end, to);
  }

  ValueMap values_;
  NonZeroList rows_, cols_;
  Coord row_count_, col_count_;
};

#endif  /* UTIL_IMMUTABLE_SPARSE_MATRIX_HPP_ */

Pour simplifier, c'est immutable, mais vous pouvez le rendre mutable; assurez-vous de changer std::vector en std::set Si vous voulez des "insertions" efficaces et raisonnables (changer un zéro en un non-zéro).

Je suggère de faire quelque chose comme:

typedef std::tuple<int, int, int> coord_t;
typedef boost::hash<coord_t> coord_hash_t;
typedef std::unordered_map<coord_hash_t, int, c_hash_t> sparse_array_t;

sparse_array_t the_data;
the_data[ { x, y, z } ] = 1; /* list-initialization is cool */

for( const auto& element : the_data ) {
    int xx, yy, zz, val;
    std::tie( std::tie( xx, yy, zz ), val ) = element;
    /* ... */
}

Pour aider à garder vos données clairsemées, vous pouvez écrire une sous-classe de unorderd_map, dont les itérateurs sautent automatiquement (et effacent) tous les éléments avec une valeur de 0.