Care este cel mai bun mod de a crea o matrice rară în C ++?

Lucrez la un proiect care necesită manipularea unor matrici enorme, în special sumare piramidală pentru calculul copula.

Pe scurt, trebuie să ținem evidența unui număr relativ mic de valori (de obicei o valoare de 1 și, în cazuri rare, mai mult de 1) într-o mare de zerouri în matrice (matrice multidimensională).

O matrice rară permite utilizatorului să stocheze un număr mic de valori și să presupună că toate înregistrările nedefinite sunt o valoare presetată. Deoarece fizic nu este posibil să stocați toate valorile în memorie, trebuie să stocăm doar câteva elemente non-zero. Acest lucru ar putea fi de câteva milioane de intrări.

Viteza este o prioritate imensă și aș dori, de asemenea, să aleg dinamic numărul de variabile din clasă în timpul execuției.

În prezent, lucrez la un sistem care utilizează un arbore binar de căutare (b-tree) pentru a stoca intrări. Știe cineva un sistem mai bun?

0
fr hi bn

11 răspunsuri

Tabelele Hash au o inserare rapidă și o căutați. Ați putea scrie o funcție hash simplă, deoarece știți că veți avea de-a face cu numai perechi întregi ca cheile.

0
adăugat

Pentru C ++, o hartă funcționează bine. Câte milioane de obiecte nu vor fi o problemă. 10 milioane de articole au avut aproximativ 4,4 secunde și aproximativ 57 meg pe computerul meu.

Cererea mea de testare este după cum urmează:

#include 
#include 
#include 

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

Acum, pentru a alege dinamic numărul de variabile, soluția cea mai ușoară este să reprezinte indexul ca un șir , iar apoi să folosiți șirul ca o cheie pentru hartă. De exemplu, un element situat la [23] [55] poate fi reprezentat prin șirul "23,55". De asemenea, putem extinde această soluție pentru dimensiuni mai mari; cum ar fi pentru trei dimensiuni, un indice arbitrar va arăta "34,45,56". O implementare simplă a acestei tehnici este după cum urmează:

std::map data 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;
0
adăugat
Din moment ce nu a fost fixat pentru o perioadă lungă de timp, am luat libertatea de ao înlocui cu o implementare corectă.
adăugat autor celtschk, sursa
ce zici de performanta de a obtine gama de elemente din aceasta sau de a verifica dacă domeniul este pe deplin în matrice?
adăugat autor Ivan G., sursa
Implementarea operatorului
adăugat autor Whanhee, sursa
Secunde doar pentru un milion de elemente? Acest lucru pare destul de rău. Ar trebui să luați în considerare utilizarea unei funcții hashing și a unordered_map . Verificați github.com/victorprad/InfiniTAM Ei folosesc hash ((x * 73856093u) ^ (y * 19349669u) ^ (z * 83492791u)) și poate integra milioane de probe într-o rețea 3D restrânsă la framerate bune.
adăugat autor masterxilo, sursa

Cea mai bună modalitate de a implementa matrice rare este de a nu le pune în aplicare - cel puțin pe cont propriu. I-aș sugera lui BLAS (care cred că este o parte din LAPACK) care se poate ocupa de matrici cu adevărat uriașe.

0
adăugat
LAPACK este o bibliotecă pentru matrice densă. Standardul BLAS este, de asemenea, pentru matricele dense. Există un pachet Sparse BLAS (prin NIST), dar acesta este diferit de cel standard BLAS.
adăugat autor codehippo, sursa

Aici este o implementare relativ simplă care ar trebui să ofere o căutare rapidă rezonabilă (folosind o tabelă de hash), precum și repetarea rapidă a elementelor non-zero într-un rând / coloană.

// 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 
#include 
#include 
#include 
#include 
#include 
#include 

// 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
class SparseMatrix {
  struct PointHasher;
  typedef std::map< Coord, std::vector > NonZeroList;
  typedef std::pair Point;

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

  SparseMatrix() = default;

  // Reads a matrix stored in MatrixMarket-like format, i.e.:
  //   
  //   
  // ...
  // Note: the header (lines starting with '%' are ignored).
  template
  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::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::type,
                             PointHasher> ValueMap;

  struct PointHasher {
    size_t operator()(const Point& p) const {
      return p.first << (std::numeric_limits::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()));
  }

  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_ */

Pentru simplitate, este immutable , dar poți să-l mutați; asigurați-vă că schimbați std :: vector la std :: set dacă doriți o inserție rezonabilă și eficientă (schimbând un zero la altul).

0
adăugat

Lista completă a soluțiilor poate fi găsită în wikipedia. Pentru comoditate, am citat secțiunile relevante după cum urmează.

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

Dicționar de chei (DOK)

DOK constă dintr-un dicționar care hărți (rând, coloană) -pare la   valoarea elementelor. Elemente care lipsesc din dicționar   sunt considerate zero. Formatul este bun incremental   construind o matrice rară în ordine aleatorie, dar slabă pentru iterare   peste valori non-zero în ordine lexicografică. Unul de obicei   construiește o matrice în acest format și apoi convertește la altul mai mult   format eficient pentru procesare. [1]

Listă de liste (LIL)

LIL stochează o listă pe rând, fiecare intrare conținând coloana   indexul și valoarea. În mod obișnuit, aceste intrări sunt păstrate ordonate după   indexul coloanei pentru o căutare mai rapidă. Acesta este un alt format bun pentru   construcție cu matrice incrementală. [2]

Listă de coordonate (COO)

COO stochează o listă de tupluri (rând, coloană, valoare). În mod ideal, intrările   sunt sortate (după index rând, apoi indice coloană) pentru a îmbunătăți accesul aleatoriu   ori. Acesta este un alt format care este bun pentru matricea incrementală   construcție. [3]

Rând comprimat rar (format CSR, CRS sau Yale)

Rândul redus comprimat (CSR) sau formatul comprimat de stocare în rând (CRS)   reprezintă o matrice M prin trei matrice (unidimensionale)   respectiv conțin valori nonzero, extensiile rândurilor și coloana   indici. Acesta este similar cu COO, dar comprimă indici de rând, prin urmare   numele. Acest format permite acces rapid la rânduri și vectori de matrice   multiplicări (Mx).

0
adăugat

Eigen is a C++ linear algebra library that has an implementation of a sparse matrix. It even supports matrix operations and solvers (LU factorization etc) that are optimized for sparse matrices.

0
adăugat

Așa cum este un sfat: metoda care utilizează șirurile ca indici este de fapt foarte lentă. O soluție mult mai eficientă, dar altfel echivalentă ar fi utilizarea vectorilor / matricelor. Nu este absolut necesar să scrieți indicii într-un șir.

typedef vector index_t;

struct index_cmp_t : binary_function {
    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 data;
index_t i(dims);
i[0] = 1;
i[1] = 2;
// ? etc.
data[i] = 42;

Cu toate acestea, folosirea unei map nu este de fapt foarte eficientă din cauza implementării în termenii unui arbore de căutare binar echilibrat. Structurile de date cu o performanță mai bună în acest caz ar fi o tabelă hash (randomizat).

0
adăugat
@Andrew Nu destul. Acest răspuns precede C ++ 11 și, prin urmare, std :: unordered_map , de mult timp. În zilele de azi îmi recomand să folosesc aceasta din urmă, dar nu este o înlocuire de tip drop-in pentru răspunsul meu deoarece std :: vector nu pare să ofere o implementare adecvată pentru std :: hash . Acestea fiind spuse, cu excepția cazului în care indicele este de fapt dimensiune variabilă (ceea ce este puțin probabil), un std :: unordered_map > ar trebui să funcționeze din cutie (deși interfața poate fi cu sigu
adăugat autor Konrad Rudolph, sursa
aka. unordered_map
adăugat autor Andrew, sursa

Boost are o implementare template a BLAS numită uBLAS care conține o matrice rară.

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

0
adăugat

Deoarece numai valorile cu [a] [b] [c] ... [w] [x] [y] [z] au consecințe, vom stoca doar indexul, nu valoarea 1 care este aproape peste tot - aceeași + nici o modalitate de a hash-l. Observând că blestemul dimensionalității este prezent, sugerați să mergeți cu un instrument stabilit NIST sau Boost, cel puțin citiți sursele pentru a eluda gafa inutilă.

Dacă lucrarea are nevoie pentru a capta distribuțiile temporale de dependență și tendințele parametrice ale seturilor de date necunoscute, atunci o Mapă sau un B-Tree cu rădăcină unificată nu este probabil practică. Putem stoca numai indicii înșiși, hașiți dacă ordonarea (sensibilitatea pentru prezentare) poate fi subordonată reducerii domeniului de timp la momentul executării, pentru toate cele 1 valori. Deoarece alte valori decât zero sunt puține, un candidat evident pentru aceștia este structura de date pe care o puteți găsi ușor și o puteți înțelege. Dacă setul de date este într-adevăr o dimensiune vastă a universului, vă sugerez un fel de fereastră de alunecare care să gestioneze fișierele / discurile / persistente-io, transferând porțiuni de date în scopuri, după cum este necesar. (scrierea unui cod pe care îl puteți înțelege) Dacă sunteți în angajamentul de a oferi o soluție reală unui grup de lucru, acest lucru vă lasă în mâinile sistemelor de operare pentru consumatori care au scopul unic de a vă lua prânzul departe de dvs.

0
adăugat

Detalii mici în compararea indexului. Trebuie să faceți o comparație lexicografică, în caz contrar:

a= (1, 2, 1); b= (2, 1, 2);
(a

Editare: Prin urmare, comparația ar trebui probabil să fie:

return lhs.x
0
adăugat

Aș sugera să faceți ceva de genul:

typedef std::tuple coord_t;
typedef boost::hash coord_hash_t;
typedef std::unordered_map 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;
    /* ... */
}

Pentru a vă ajuta să vă păstrați datele rare, vă recomandăm să scrieți o subclasă de unorderd_map , ale cărei iteratori să sări peste (și să ștergă) toate elementele cu valoarea 0.

0
adăugat