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



oop data-structures (8)

A lista completa de soluções pode ser encontrada na wikipedia. Por conveniência, citei seções relevantes da seguinte forma.

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

Dicionário de chaves (DOK)

DOK consiste em um dicionário que mapeia (linha, coluna) - emparelha com o valor dos elementos. Os elementos ausentes do dicionário são considerados zero. O formato é bom para construir incrementalmente uma matriz esparsa em ordem aleatória, mas ruim para iterar sobre valores diferentes de zero em ordem lexicográfica. Normalmente, constrói-se uma matriz nesse formato e depois se converte em outro formato mais eficiente para processamento. [1]

Lista de listas (LIL)

O LIL armazena uma lista por linha, com cada entrada contendo o índice da coluna e o valor. Normalmente, essas entradas são mantidas classificadas pelo índice da coluna para uma pesquisa mais rápida. Este é outro formato bom para construção de matriz incremental. [2]

Lista de coordenadas (COO)

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

Linha esparsa compactada (formato CSR, CRS ou Yale)

O formato de linha esparsa compactada (CSR) ou armazenamento de linha compactada (CRS) representa uma matriz M por três matrizes (unidimensionais), que contêm valores diferentes de zero, as extensões de linhas e índices de coluna, respectivamente. É semelhante ao COO, mas compacta os índices de linha, daí o nome. Esse formato permite acesso rápido a linhas e multiplicações de vetores de matriz (Mx).

Estou trabalhando em um projeto que requer a manipulação de enormes matrizes, especificamente somatório piramidal para um cálculo de cópula.

Em resumo, eu preciso acompanhar um número relativamente pequeno de valores (geralmente um valor de 1 e, em casos raros, mais de 1) em um mar de zeros na matriz (matriz multidimensional).

Uma matriz esparsa permite que o usuário armazene um pequeno número de valores e assuma que todos os registros indefinidos sejam um valor predefinido. Como não é possível armazenar fisicamente todos os valores na memória, preciso armazenar apenas os poucos elementos diferentes de zero. Isso pode 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.

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


Answer #1

A melhor maneira de implementar matrizes esparsas é não implementá-las - pelo menos não por conta própria. Eu sugeriria ao BLAS (que eu acho que faz parte do LAPACK) que pode lidar com matrizes realmente grandes.


Answer #2

As tabelas de hash têm uma inserção rápida e procuram. Você pode escrever uma função simples de hash, pois sabe que lidaria apenas com pares inteiros como chaves.


Answer #3

Como apenas os valores com [a] [b] [c] ... [w] [x] [y] [z] são importantes, armazenamos apenas o próprio índice, não o valor 1 que está em quase todo lugar - sempre o mesmo + não há como fazer hash. Observando que a maldição da dimensionalidade está presente, sugira ir com alguma ferramenta estabelecida NIST ou Boost, pelo menos leia as fontes para contornar esse erro desnecessário.

Se o trabalho precisar capturar as distribuições de dependência temporal e tendências paramétricas de conjuntos de dados desconhecidos, um mapa ou uma árvore B com raiz unvalorizada provavelmente não é prático. Podemos armazenar apenas o próprio índice, com hash, se a ordem (sensibilidade para apresentação) puder subordinar à redução do domínio do tempo no tempo de execução, para todos os 1 valores. Como os valores diferentes de zero, exceto um, são poucos, um candidato óbvio para esses é qualquer estrutura de dados que você possa encontrar e entender rapidamente. Se o conjunto de dados tiver um tamanho verdadeiramente amplo, sugiro algum tipo de janela deslizante que gerencia você mesmo o arquivo / disco / persistente, movendo partes dos dados para o escopo, conforme necessário. (escrevendo um código que você possa entender) Se você se comprometer a fornecer uma solução real para um grupo de trabalho, deixar de fazê-lo fica à mercê de sistemas operacionais de nível consumidor que têm o único objetivo de levar seu almoço longe de você.


Answer #4

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 dados escassos, você pode escrever uma subclasse de unorderd_map , cujos iteradores pulam automaticamente (e apagam) qualquer item com o valor 0.



Answer #6

Pequenos detalhes na comparação do índice. Você precisa fazer uma comparação lexicográfica, caso contrário:

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

Edit: Portanto, a comparação provavelmente deve 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

Answer #7

Eigen é uma biblioteca de álgebra linear C ++ que possui uma implementation de uma matriz esparsa. Ele ainda suporta operações e solucionadores de matrizes (fatoração de LU, etc.) otimizados para matrizes esparsas.





maps