Qual é a melhor maneira de criar uma matriz esparsa em C ++?

votos
44

Eu estou trabalhando em um projeto que exige a manipulação de grandes matrizes, especificamente somatório piramidal para um cálculo de cópula.

Em suma, preciso para manter um registo de um número relativamente pequeno de valores (geralmente um valor de 1, e em casos raros, mais do que um) em um mar de zeros na matriz (matriz multidimensional).

Uma matriz esparsa permite ao utilizador armazenar um pequeno número de valores, e assumir todos os registos indefinidos para ser um valor pré-determinado. Como não é fisicamente possivelmente para armazenar todos os valores na memória, eu preciso armazenar apenas os poucos elementos diferentes de zero. Isso poderia ser de vários milhões de entradas.

A velocidade é uma grande prioridade, e eu também gostaria de escolher dinamicamente o número de variáveis ​​na classe em tempo de execução.

Eu atualmente trabalho em um sistema que usa uma árvore de busca binária (b-tree) para armazenar entradas. Alguém sabe de um melhor sistema?

Publicado 07/08/2008 em 03:29
fonte usuário
Em outras línguas...                            


11 respostas

votos
25

Para C ++, um mapa funciona bem. Vários milhões de objetos não será um problema. 10 milhões de itens levou cerca de 4,4 segundos e cerca de 57 meg no meu computador.

Meu aplicativo de teste é o seguinte:

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

Agora, para escolher dinamicamente o número de variáveis, a solução mais fácil é para representar o índice como uma string , e então usar cordas como uma chave para o mapa. Por exemplo, um item localizado na [23] [55] pode ser representado através de "23,55" string. Também pode estender esta solução para dimensões mais elevadas; como por três dimensões um índice arbitrário será semelhante "34,45,56". A simples implementação desta técnica é a seguinte:

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;
Respondeu 07/08/2008 em 03:33
fonte usuário

votos
16

Assim como um conselho: o método usando cordas como índices é realmente muito lento. Uma solução muito mais eficiente, mas de outra forma equivalente seria a utilização de vectores / matrizes. Não há absolutamente nenhuma necessidade de escrever os índices em uma string.

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;

No entanto, usando um mapnão é realmente muito eficiente por causa da implementação em termos de uma árvore de pesquisa balanceada binário. Muito melhores estruturas de dados que executam em neste caso seria um (ao acaso) tabela hash.

Respondeu 02/09/2008 em 09:53
fonte usuário

votos
11

Impulso tem uma implementação de modelo de Blas chamado uBLAS que contém uma matriz esparsa.

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

Respondeu 22/08/2008 em 00:45
fonte usuário

votos
4

Pequeno detalhe na comparação de índice. Você precisa fazer um lexicographical comparar, de outra forma:

a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a

Edit: Então, a comparação deve provavelmente 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
Respondeu 19/08/2008 em 22:59
fonte usuário

votos
3

Eigen é uma biblioteca ++ álgebra linear C, que tem uma aplicação de uma matriz escasso. É ainda suporta operações de matriz e agentes de resolução (LU fatoração etc.) que foram optimizadas para matrizes esparsas.

Respondeu 29/12/2014 em 21:23
fonte usuário

votos
3

As tabelas de hash têm uma inserção rápida e olhar para cima. Você poderia escrever uma função hash simples, já que você sabe que você estaria lidando com apenas pares de inteiros como as chaves.

Respondeu 07/08/2008 em 04:13
fonte usuário

votos
2

lista completa de soluções podem ser encontradas na wikipedia. Por conveniência, citei secções relevantes da seguinte forma.

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

Dicionário de chaves (DOK)

DOK consiste de um dicionário que mapeia (linha, coluna) -pairs ao valor dos elementos. Elementos que estão faltando a partir do dicionário são tidas como zero. O formato é bom para incrementalmente construção de uma matriz esparsa em ordem aleatória, mas pobre para iteração sobre valores diferentes de zero em ordem lexicográfica. Um tipicamente constrói uma matriz com este formato e, em seguida, converte para outro formato mais eficiente para o processamento. [1]

Lista de listas (LIL)

lojas LIL uma lista de cada linha, com cada entrada contendo o índice de coluna e o valor. Tipicamente, estas entradas são mantidas classificados pelo índice de coluna para pesquisa de mais rápido. Este é um outro formato de bom para a construção da matriz incremental. [2]

lista de coordenadas (COO)

COO armazena uma lista de (linha, coluna, valor) tuplas. Idealmente, as entradas são classificados (por índice de linha, então o índice de coluna) para melhorar os tempos de acesso aleatório. Este é um outro formato que é bom para a construção da matriz incremental. [3]

Comprimido linha esparsa (CSR, CRS ou formato de Yale)

A linha comprimido escasso (RSE) ou formato de armazenamento de fileira comprimido (CRS) representa uma matriz M por três matrizes (unidimensional), que contêm, respectivamente, valores diferentes de zero, as extensões de linhas, e os índices de colunas. É semelhante ao COO, mas comprime os índices de linha, daí o nome. Este formato permite acesso de linha rápido e multiplicações matriz-vetor (MX).

Respondeu 07/12/2016 em 18:06
fonte usuário

votos
1

A melhor maneira de implementar matrizes esparsas é para não implementá-las - pelo menos não em seu próprio país. Gostaria de sugerir a BLAS (que eu acho que é uma parte do LAPACK) que pode lidar com muito grandes matrizes.

Respondeu 08/08/2008 em 07:11
fonte usuário

votos
0

Eu sugeriria fazer 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 ajudar a manter os seus dados esparsos, você pode querer escrever uma subclasse de unorderd_map, cuja iterators pular automaticamente ao longo (e apagar) quaisquer itens com um valor de 0.

Respondeu 12/10/2016 em 01:31
fonte usuário

votos
0

Aqui é uma implementação relativamente simples, que deve fornecer uma pesquisa razoável rápido (usando uma tabela hash), bem como iteração rápida sobre elementos diferentes de zero em uma linha / coluna.

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

Para simplificar, é immutable, mas você pode pode torná-lo mutável; certifique-se de mudar std::vectorpara std::setse você quer um razoáveis "inserções" eficientes (mudando um zero a um diferente de zero).

Respondeu 23/06/2014 em 16:59
fonte usuário

votos
0

Uma vez que apenas valoriza com [a] [b] [c] ... [w] [x] [y] [z] são de conseqüência, temos apenas armazenar o indice si mesmos, não o valor 1, que é quase todos os lugares - sempre o mesmo + nenhuma maneira de hash-lo. Notando que a maldição da dimensionalidade está presente, sugiro ir com alguns NIST ferramenta estabelecida ou Boost, pelo menos ler as fontes para que contornar erro desnecessário.

Se o trabalho precisa capturar as distribuições dependência temporal e tendências paramétricos de conjuntos de dados desconhecidos, em seguida, um mapa ou uma B-árvore com raiz valorizado-uni provavelmente não é prático. Podemos armazenar apenas o indice si, hash se ordenação (sensibilidade para a apresentação) pode subordinar a redução do domínio de tempo em tempo de execução, para todos os 1 valores. Desde valores diferentes de zero outros do que um são poucos, um candidato óbvio para aqueles é whatever-estrutura de dados que você pode encontrar facilmente e compreender. Se o conjunto de dados é verdadeiramente vasto universo-dimensionados sugiro algum tipo de janela deslizante que gerencia arquivos / disco / persistent-io-se, movendo-se partes dos dados em âmbito como necessário. (Escrevendo código que você possa entender) Se você estiver sob compromisso de fornecer a solução real para um grupo de trabalho,

Respondeu 27/09/2009 em 18:52
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more