Was ist der beste Weg, um erstellen Sie eine sparse-array in C++?
https://stackoverflow.com/questions/4306
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich arbeite an einem Projekt, das erfordert, dass die manipulation von riesigen Matrizen, speziell pyramidal Summe für eine copula Berechnung.
Kurzum, ich brauche zu halten track von einer relativ kleinen Anzahl von Werten (in der Regel ein Wert von 1, und in seltenen Fällen mehr als 1) in einem Meer von Nullen in der matrix (mehrdimensionale Arrays).
Eine sparse-array erlaubt die Speicherung einer geringen Anzahl von Werten, und übernehmen alle undefined Aufzeichnungen eines preset-Wertes.Denn es ist nicht körperlich möglicherweise zum speichern aller Werte im Speicher, muss ich nur die wenigen nicht-null-Elemente.Dies könnte mehrere Millionen Einträge.
Geschwindigkeit ist eine große Priorität, und ich möchte auch dynamisch wählen Sie die Anzahl der Variablen in der Klasse zur Laufzeit.
Ich arbeite derzeit an einem system, dass verwendet eine binäre Suchbaum (b-tree) zum speichern von Einträgen.Kennt jemand ein besseres system?
Lösung
Für C++, eine Karte, die gut funktioniert.Mehrere Millionen Objekte werden nicht ein problem.10 Millionen Stück dauerte etwa 4,4 Sekunden und etwa 57 meg auf meinem computer.
Mein test-Anwendung ist wie folgt:
#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;
}
Nun dynamisch wählen Sie die Anzahl der Variablen, ist die einfachste Lösung darstellen index als string, und dann die Verwendung von string als Schlüssel für die map.Zum Beispiel, ein Element, das sich an [23][55] dargestellt werden kann, über "23,55" string.Wir können auch erweitern, diese Lösung auch für höhere Dimensionen;wie für die drei Dimensionen eine beliebige index-Aussehen wird "34,45,56".Eine einfache Implementierung dieser Technik ist wie folgt:
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;
Andere Tipps
Als eine Allgemeine Beratung, eine Methode mit strings als Indizes ist tatsächlich sehr langsam.Eine viel mehr effiziente, aber sonst gleichwertige Lösung wäre die Verwendung von Vektoren/arrays.Es gibt absolut keine Notwendigkeit zu schreiben, die Indizes, die in einer Zeichenfolge.
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;
Jedoch, mit eine map in der Praxis ist oft nicht sehr effizient, da von der Umsetzung im Sinne einer balancierten binären Suchbaum.Eine bessere Durchführung von Daten-Struktur in diesem Fall wäre eine hash-Tabelle, wie Sie std::unordered_map.
Boost hat eine vorgefertigte Implementierung von BLAS genannt uBLAS enthält eine spärliche matrix.
http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm
Kleine Details in den index-Vergleich.Sie müssen zu tun eine lexikographische vergleichen, ansonsten:
a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a
Edit:So ist der Vergleich sollte wohl sein:
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
Hash-Tabellen sind ein schnelles einfügen und schauen.Sie können eine einfache hash-Funktion, da Sie wissen, Sie würden es mit nur integer-Paare wie die Tasten.
Vollständige Liste der Lösungen können gefunden werden in die wikipedia.Für die Bequemlichkeit, die ich zitiert habe relevanten Abschnitte wie folgt.
https://en.wikipedia.org/wiki/Sparse_matrix#Dictionary_of_keys_.28DOK.29
Wörterbuch der Tasten (DOK)
DOK besteht aus einem Wörterbuch, dass die Karten (Zeile, Spalte)-Paare zu den Wert der Elemente.Fehlende Elemente, die aus dem Wörterbuch werden zu null angenommen.Das format ist gut für schrittweise Bau einer sparse matrix in zufälliger Reihenfolge, aber schlecht für die Iteration über nicht-null-Werte in lexikographische Reihenfolge.Eine Regel konstruiert eine matrix, die in diesem format und konvertiert Sie in eine weitere effizientes format für die Bearbeitung.[1]
Liste der Listen (LIL)
LIL speichert eine Liste pro Zeile, jeder Eintrag enthält die Spalte index und den Wert.In der Regel werden diese Einträge sind gehalten sortiert nach Spalte index zur schnelleren Suche.Dies ist ein weiteres format gut für inkremental-matrix-Konstruktion.[2]
Koordinatenliste (COO)
COO speichert eine Liste von (Zeile, Spalte, Wert) - Tupeln.Idealerweise werden die Einträge sortiert werden (nach Zeile index, dann Spalte index) zu verbessern random access mal.Dies ist ein weiteres format, das gut für inkrementelle matrix Bau.[3]
Compressed sparse row (CSR, CRS oder Yale format)
Die compressed sparse row (CSR) oder compressed row storage (CRS) format repräsentiert eine matrix M, die durch drei (eindimensionalen) arrays, dass jeweils enthalten Werte ungleich null, die Blöcke von Zeilen-und Spalten - Indizes.Es ist ähnlich wie COO, aber komprimiert die Zeile Indizes, also der name.Dieses format ermöglicht schnellen row access-und matrix-Vektor - Multiplikationen (Mx).
Der beste Weg, um zu implementieren, sparse-Matrizen ist nicht, um Sie zu implementieren - atleast nicht auf Ihre eigenen.Ich würde vorschlagen, zu BLAS (was ich denke, ist ein Teil von LAPACK), die mit wirklich riesigen Matrizen.
Da nur Werte mit [a], [b], [c],...[w][x][y][z] sind in der Folge, wir speichern nur den indice sich, nicht den Wert 1, die nur über überall - immer die gleichen + kein Weg zu Hashen.Feststellend, dass der Fluch der Dimensionalität vorhanden ist, schlagen Sie mit einigen etablierten tool NIST-oder Boost, zumindest Lesen Sie die Quellen für diese zu umgehen, unnötige Patzer.
Wenn die die Arbeit muss zum erfassen der zeitlichen Abhängigkeit Distributionen und parametrische Tendenzen der unbekannte Datensätze, dann eine Karte oder ein B-Baum mit uni-geschätzt, root wird wahrscheinlich nicht praktisch.Wir speichern nur die indice sich, Hash, wenn der Bestellung ( Sensibilität für die Präsentation ) können untergeordnet Reduzierung der time domain at run-time, für alle 1-Werte.Da nicht-null-Werte anderen als ein paar, ein offensichtlicher Kandidat für diese ist unabhängig von Daten-Struktur können Sie leicht finden und verstehen.Wenn die Daten set ist wirklich riesig-Universum sized ich schlage vor, eine Art von Schiebe-Fenster verwaltet die Datei / Festplatte / persistent-io selbst, bewegten Teile der Daten in Umfang, wie es sein muss.( schreiben von code, Sie verstehen können ) Wenn Sie unter Verpflichtung zur tatsächlichen Lösung für eine Arbeitsgruppe, Ausfall zu tun so lässt Sie der Gnade der consumer-grade-Betriebssysteme, die das alleinige Ziel, Ihr Mittagessen von Ihnen Weg.
Hier ist eine relativ einfache Implementierung, sollte eine vernünftige schnelle lookup (eine hash-Tabelle) sowie einen schnellen iteration über nicht-null-Elemente in einer Zeile/Spalte.
// 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_ */
Für Einfachheit, es ist immutable, aber Sie können es machen kann, veränderlich;sicher sein, zu ändern std::vector zu std::set wenn Sie möchten, dass eine angemessene effiziente "Einschübe" (ändern einer null zu einem nicht-null).
Ich würde vorschlagen, etwas zu tun wie:
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;
/* ... */
}
Zum Schutz Ihrer Daten spärlich, Sie möchten vielleicht schreiben Sie eine Unterklasse von unorderd_map, dessen Iteratoren automatisch überspringen (und löschen) werden alle Elemente mit dem Wert 0.
