¿Cuál es la mejor forma de crear una matriz dispersa en C++?
https://stackoverflow.com/questions/4306
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy trabajando en un proyecto que requiere la manipulación de enorme matrices, específicamente piramidal de la suma de una cópula de cálculo.
En resumen, tengo que hacer un seguimiento de un número relativamente pequeño de valores (normalmente un valor de 1, y en raros casos de: 1) en un mar de ceros en la matriz (matriz multidimensional).
Una matriz dispersa permite al usuario almacenar un número pequeño de valores, y asumir todas las indefinido, los registros a ser de un valor preestablecido.Ya no es físicamente posiblemente para almacenar todos los valores en la memoria, necesito almacenar sólo los pocos no-cero elementos.Esta puede ser de varios millones de entradas.
La velocidad es una gran prioridad, y también me gustaría elegir dinámicamente el número de variables en la clase en tiempo de ejecución.
Actualmente trabajo en un sistema que utiliza un árbol de búsqueda binario (b-tree) para almacenar entradas.¿Alguien sabe de un mejor sistema?
Solución
Para C++, un mapa funciona bien.Varios millones de objetos no será un problema.10 millones de artículos tomó alrededor de 4,4 segundos y 57 meg en mi equipo.
Mi aplicación de prueba es como sigue:
#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;
}
Ahora a elegir dinámicamente el número de variables, la solución más sencilla es la de representar índice como una cadena, y , a continuación, utilizar la cadena como clave para el mapa.Por ejemplo, un elemento ubicado en [23][55] puede ser representado a través de "23,55" de la cadena.También podemos extender esta solución para dimensiones superiores;como para tres dimensiones arbitrarias índice se verá como "34,45,56".Una simple aplicación de esta técnica es el siguiente:
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;
Otros consejos
Como consejo general, un método que utiliza las cadenas como los índices es en realidad muy lento.Una forma mucho más eficiente, pero de otra manera equivalente de la solución sería el uso de vectores/matrices.No hay absolutamente ninguna necesidad de escribir los índices en una cadena.
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;
Sin embargo, el uso de un map en la práctica, a menudo no es muy eficiente debido a la implementación en términos de una equilibrada árbol de búsqueda binario.Mejorar el rendimiento de la estructura de datos en este caso sería una tabla hash, como la proporcionada por std::unordered_map.
Boost tiene una plantilla de aplicación de BLAS llamado uBLAS que contiene una matriz dispersa.
http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm
Pequeño detalle en el índice de comparación.Usted necesita hacer un lexicográfica, comparar, de lo contrario:
a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a
Editar:De manera que la comparación debería de ser:
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
Las tablas Hash tiene una inserción rápida y mirar hacia arriba.Podría escribir una simple función de hash, ya que usted sabe que usted estaría tratando con sólo enteros pares como las llaves.
Eigen es un C++ de álgebra lineal de la biblioteca que tiene una la aplicación de una matriz dispersa.Incluso soporta las operaciones de matriz y solucionadores (factorización LU etc) que están optimizados para matrices dispersas.
Lista completa de las soluciones se pueden encontrar en la wikipedia.Para mayor comodidad, he citado las secciones pertinentes de la siguiente manera.
https://en.wikipedia.org/wiki/Sparse_matrix#Dictionary_of_keys_.28DOK.29
Diccionario de claves (DOK)
DOK consta de un diccionario que mapea (fila, columna) pares de la valor de los elementos.Los elementos que faltan en el diccionario se toma como cero.El formato es bueno para incrementalmente la construcción de una matriz dispersa en orden aleatorio, pero pobre para recorrer sobre valores distintos de cero en orden lexicográfico.Uno normalmente construye una matriz en este formato y, a continuación, convierte a otro más formato eficiente para el procesamiento.[1]
Lista de listas (LIL)
LIL almacena una lista por fila, con cada entrada que contiene la columna índice y el valor.Normalmente, estas entradas se mantienen ordenados por columna de índice para agilizar la búsqueda.Este es otro formato de bueno para incremental de la matriz de la construcción.[2]
Coordinar lista (COO)
COO almacena una lista de (fila, columna, valor) tuplas.Idealmente, las entradas se ordenan (por índice de fila, entonces el índice de columna) para mejorar el acceso aleatorio veces.Este es otro formato que es bueno para incremental de la matriz de la construcción.[3]
Comprimido escasa fila de las empresas (RSE), CRS o Yale formato)
El comprimido escasa fila de las empresas (RSE) o comprimido fila de almacenamiento (CRS) formato de representa una matriz M por tres (unidimensional) de matrices, que respectivamente, contienen valores distintos de cero, la extensión de filas y de columnas los índices.Es similar a la de director de operaciones, pero comprime la fila de los índices, por lo tanto el nombre.Este formato permite un rápido acceso a las filas de la matriz y vector multiplicaciones (Mx).
La mejor manera de aplicar las matrices dispersas es no aplicar ellos - al menos no en su propia.Yo sugeriría a BLAS (que creo que es una parte de LAPACK) que puede manejar un gran matrices.
Dado que sólo los valores de [a][b][c]...[w][x][y][z] son de consecuencia, sólo guardamos el indice de sí mismos, no el valor 1, que es casi siempre la misma + no hay manera de hash.Tomando nota de que la maldición de la dimensionalidad está presente, sugieren ir con alguna herramienta establecida NIST o refuerzo, al menos leer las fuentes que para eludir la huelga metedura de pata.
Si el trabajo necesita para capturar la dependencia temporal de las distribuciones paramétricas y las tendencias de las que se desconoce conjuntos de datos, a continuación, un Mapa o un B-Árbol con uni-valores de raíz, probablemente no es práctico.Podemos almacenar sólo el indice de sí mismos, hash, si el pedido ( sensibilidad para la presentación ) puede subordinar a la reducción del dominio de tiempo en tiempo de ejecución, para todos los valores 1.Desde valores distintos de cero, otros que son pocos, un candidato obvio para aquellos que es lo que la estructura de datos que usted puede encontrar fácilmente y entender.Si el conjunto de datos es realmente enorme-universo de tamaño me sugieren algún tipo de ventana deslizante que gestiona el archivo / disco / persistent-io a ti mismo, mover partes de los datos en el ámbito según sea su necesidad.( escribir el código que se puede entender ) Si eres menor de compromiso de dar solución real a un grupo de trabajo, de no hacerlo, te deja a la merced de los consumidores de grado sistemas operativos que tienen el único objetivo de tomar su almuerzo de distancia de usted.
Aquí es una operación relativamente sencilla aplicación que debe proporcionar una razonable búsqueda rápida (usando una tabla de hash), así como una rápida iteración sobre los no-cero de los elementos en una fila/columna.
// 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_ */
Por simplicidad, es immutable, pero puede hacer es mutable;asegúrese de cambiar std::vector a std::set si desea una razonable eficiente "inserciones" (cambio de un cero a un valor distinto de cero).
Yo sugeriría hacer algo como:
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;
/* ... */
}
Para ayudar a mantener sus datos dispersos, usted podría querer escribir una subclase de unorderd_map, cuya iteradores automáticamente saltar (y borrar) los elementos con un valor de 0.
