Qual è il modo migliore per creare una matrice sparsa in C++?
https://stackoverflow.com/questions/4306
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto lavorando su un progetto che richiede la manipolazione di enorme matrici, in particolare piramidale sommatoria per una copula di calcolo.
In breve, ho bisogno di tenere traccia di un numero relativamente piccolo di valori (di solito un valore di 1, e, in rari casi, più che 1) in un mare di zeri nella matrice (array multidimensionale).
Una matrice sparsa consente all'utente di memorizzare un numero limitato di valori, e si assume tutti definito il record di essere un valore preimpostato.Poiché non è fisicamente forse per memorizzare tutti i valori in memoria, ho bisogno di memorizzare solo i pochi non-zero elementi.Questo potrebbe essere di parecchi milioni di voci.
La velocità è una priorità enorme, e vorrei anche scegliere dinamicamente il numero di variabili in classe in fase di runtime.
Attualmente lavoro su un sistema che utilizza un albero di ricerca binaria (b-tree) per memorizzare le voci.Qualcuno conosce un sistema migliore?
Soluzione
Per il C++, è una mappa che funziona bene.Diversi milioni di oggetti che non sarà un problema.10 milioni di elementi voluti circa 4,4 secondi e circa il 57 meg sul mio computer.
La mia applicazione di test è il seguente:
#include <stdio.h>
#include <stdlib.h>
#include <map>
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;
}
Ora per scegliere dinamicamente il numero di variabili, la soluzione più semplice è quello di rappresentare l'indice come una stringa, e quindi utilizzare la stringa come una chiave per la mappa.Per esempio, un elemento che si trova in [23][55] può essere rappresentato tramite "23,55" stringa.Si può anche estendere questa soluzione per dimensioni superiori;come per le tre dimensioni di un indice arbitrario sarà simile a "34,45,56".Una semplice implementazione di questa tecnica è la seguente:
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;
Altri suggerimenti
Come consiglio generale, un metodo che utilizza le stringhe di indici come è in realtà molto lento.Un modo molto più efficiente, ma in caso contrario equivalente soluzione sarebbe usare i vettori/matrici.Non c'è assolutamente alcuna necessità di scrivere gli indici in una stringa.
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;
Tuttavia, utilizzando un map in pratica spesso non è molto efficiente a causa dell'attuazione in termini di equilibrio binary search tree.Una migliore esecuzione di una struttura di dati in questo caso sarebbe una tabella hash, come previsto dalla std::unordered_map.
Boost è un basato su modelli di attuazione di BLAS chiamato uBLAS che contiene una matrice sparsa.
http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm
Piccoli dettagli in un indice di confronto.Hai bisogno di fare un confronto lessicografico, altrimenti:
a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a
Edit:Così il confronto, probabilmente, dovrebbe essere:
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
Le tabelle Hash di un inserimento rapido e guardare in alto.Si potrebbe scrivere una semplice funzione di hash dal momento che si sa che si avrebbe a che fare con un solo numero intero più coppie di chiavi.
Eigen è un C + + libreria di algebra lineare che ha un attuazione di una matrice sparsa.Supporta anche le operazioni di matrici e solutori (fattorizzazione LU, ecc) che sono ottimizzati per matrici sparse.
Lista completa di soluzioni si possono trovare anche su wikipedia.Per comodità, ho citato pertinenti sezioni come segue.
https://en.wikipedia.org/wiki/Sparse_matrix#Dictionary_of_keys_.28DOK.29
Dizionario di tasti (DOK)
DOK si compone di un dizionario che mappa (riga, colonna)-coppie per l' valore degli elementi.Elementi che mancano dal dizionario sono considerate pari a zero.Il formato è un bene per il modo incrementale la costruzione di una matrice sparsa in ordine casuale, ma poveri per la ripetizione su valori diversi da zero in ordine lessicografico.In genere costruisce una matrice in questo formato e quindi converte a un'altra più efficiente formato per l'elaborazione.[1]
Lista di liste (LIL)
LIL memorizza una lista per ogni riga, ogni voce contenente la colonna indice e il valore.In genere, queste voci sono tenuti ordinati per indice di colonna per una più veloce ricerca.Questo è un altro formato di buono per incrementale costruzione di matrice.[2]
Elenco di Coordinate (COO)
COO memorizza un elenco di (riga, colonna, valore) tuple.Idealmente, le voci sono ordinati (con indice di riga, quindi indice di colonna) per migliorare l'accesso casuale volte.Questo è un altro formato che è buono per la incrementale matrice costruzione.[3]
Compressa sparse fila (RSI, CRS o Yale formato)
Compressa sparse fila (CSR) o compresso archiviazione di riga (CRS) formato rappresenta una matrice M da tre (unidimensionale) le matrici, che rispettivamente contengono valori diversi da zero, e l'estensione delle righe e delle colonne gli indici.È simile a COO, ma comprime la riga indici, quindi il nome.Questo formato permette un rapido accesso riga e matrice-vettore moltiplicazioni (Mx).
Il modo migliore per implementare matrici sparse per non metterle in atto - almeno non sul proprio.Vorrei suggerire di BLAS (che credo sia una parte di CODICE), che in grado di gestire davvero enorme matrici.
Dal momento che solo i valori con [a][b][c]...[w][x][y][z] sono, di conseguenza, ci limitiamo a memorizzare l'indice stessi, non il valore 1 che è appena circa dovunque - sempre lo stesso + modo di hash.Notare che la maledizione della dimensionalità è presente, suggerisco di andare con alcuni tool NIST o Boost, almeno a leggere le fonti che per aggirare inutile abbaglio.
Se il lavoro deve acquisire la dipendenza temporale distribuzioni parametriche e tendenze di unknown insiemi di dati, una Mappa o di un B-Albero con uni con valori di root, probabilmente, non è pratico.Siamo in grado di memorizzare solo l'indice stessi, hash se ordinazione ( sensibilità per la presentazione ) può subordinata alla riduzione del tempo di dominio in fase di esecuzione, per tutti i 1 i valori.Dato che i non-valori zero altro che non sono pochi, un candidato più ovvio per chi ha qualsiasi tipo di dati-struttura, è possibile trovare facilmente e capire.Se il set di dati è veramente vasto universo di dimensioni suggerisco una sorta di finestra scorrevole che gestisce file / disco / persistent-io di te, lo spostamento di porzioni di dati in ambito come necessario.( scrittura di codice che si può capire ), Se hai meno di impegno per fornire la soluzione di un gruppo di lavoro, in caso contrario ti lascia in balia del grado di consumo di sistemi operativi che hanno il solo obiettivo di prendere il vostro pranzo di distanza da voi.
Qui è relativamente semplice attuazione, che dovrebbe fornire una ragionevole veloce ricerca (utilizzando una tabella di hash), nonché di fast iterazione su non-zero elementi in una riga/colonna.
// 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_ */
Per semplicità, è immutable, ma si può rendere modificabile;assicurarsi di cambiare std::vector per std::set se si desidera un ragionevole efficiente "inserimenti" (cambiando il valore zero per un non-zero).
Vorrei suggerire di fare qualcosa di simile:
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;
/* ... */
}
Per aiutare a mantenere i vostri dati sparsi, si potrebbe desiderare di scrivere una sottoclasse di unorderd_map, cui gli iteratori automaticamente saltare (e cancellare) oggetti con un valore di 0.
