Usando uma matriz esparsa versus matriz numérica

Jul 20, 2021
admin

O pacote scipy matriz esparsa, e similares no MATLAB, foi baseado em idéias desenvolvidas a partir de problemas de álgebra linear, como a resolução de grandes equações lineares esparsas (por exemplo, diferenças finitas e implementações de elementos finitos). Assim coisas como produto de matriz (o produto dot produto para matrizes numéricas) e solucionadores de equações estão bem desenvolvidos.

A minha experiência aproximada é que um produto de matriz esparsa csr tem que ter uma sparsity de 1% para ser mais rápido que a densa operação equivalente dot – em outras palavras, um valor não zero para cada 99 zeros. (mas veja os testes abaixo)

mas as pessoas também tentam usar matrizes esparsas para salvar a memória. Mas tenha em mente que tal matriz tem que armazenar 3 matrizes de valores (pelo menos no formato coo). Então a sparsity tem que ser menor que 1/3 para começar a salvar a memória. Obviamente você não vai salvar memória se primeiro construir o array denso, e criar o sparse a partir dele.

O pacote scipy implementa muitos formatos esparsos. O formato coo é o mais fácil de entender e construir. Construa um de acordo com a documentação e veja seus atributos .data, .row, e .col (3 arrays 1d).

csr e csc são tipicamente construídos a partir do formato coo, e comprima os dados um pouco, tornando-os um pouco mais difíceis de entender. Mas eles têm a maior parte da funcionalidade matemática.

Também é possível indexar o formato csr, embora em geral isso seja mais lento que o caso equivalente de matriz densa/arranjo. Outras operações como mudança de valores (especialmente de 0 para não zero), concatenação, crescimento incremental, também são mais lentas.

lil (listas de listas) também é fácil de entender, e o melhor para construção incremental. dok é realmente uma subclasse do dicionário.

Um ponto chave é que uma matriz esparsa é limitada a 2d, e de muitas maneiras comporta-se como a classe np.matrix (embora não seja uma subclasse).

Uma busca por outras questões usando scikit-learn e sparse pode ser a melhor maneira de encontrar os prós/cons de usar estas matrizes. Já respondi a várias perguntas, mas conheço o lado ‘esparso’ melhor do que o lado ‘aprender’. Eu acho que elas são úteis, mas eu percebo que o ajuste nem sempre é o melhor. Qualquer customização está no lado learn. Até agora o pacote sparse não foi otimizado para esta aplicação.

Tentei alguns testes de produtos de matriz, usando o método sparse.random para criar uma matriz esparsa com uma sparsity especificada. A multiplicação de matrizes esparsas foi melhor do que eu esperava.

In : M=sparse.random(1000,1000,.5)In : timeit M1=M*M1 loops, best of 3: 2.78 s per loopIn : timeit Ma=M.toarray(); M2=Ma.dot(Ma)1 loops, best of 3: 4.28 s per loop

É um problema de tamanho; para matrizes menores a densa dot é mais rápida

In : M=sparse.random(100,100,.5)In : timeit M1=M*M100 loops, best of 3: 3.24 ms per loopIn : timeit Ma=M.toarray(); M2=Ma.dot(Ma)1000 loops, best of 3: 1.44 ms per loop

Mas comparar indexação

In : timeit M.tocsr()10 loops, best of 3: 86.4 ms per loopIn : timeit Ma1000000 loops, best of 3: 318 ns per loopIn : timeit Ma=M.toarray();Ma10 loops, best of 3: 23.6 ms per loop

Deixe uma resposta

O seu endereço de email não será publicado.