Usando uma matriz esparsa versus matriz numérica
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