Dlaczego lil_matrix i dok_matrix są tak powolne w porównaniu do zwykłego dyktowania dyktowanych?

Question

Chcę iteracyjnie budować macierze rzadkie, i zauważył, że istnieją dwa odpowiednie opcje to zgodnie z dokumentacją scipy:

LiL matrix:

klasy scipy.sparse.lil_matrix (arg1, kształt = None , dtype = Brak, copy = False) [źródło] Lista rzadka połączona wierszami

Jest to wydajna struktura do budowania rzadkich macierzy przyrostowo.

DoK matrix:

klasy scipy.sparse.dok_matrix (arg1, kształt = None, dtype = None, kopii = False) [źródło] Słownik kluczy podstawie macierz rzadką.

Jest to wydajna struktura do budowania rzadkich macierzy przyrostowo.

Ale kiedy biegnę odniesienia w stosunku do budowy słownika słownika wartości (które później można łatwo przekształcić do rozrzedzony matrycy), ten ostatni okazuje się około 10-20 razy szybciej niż przy użyciu dowolnego rzadki modele macierzy:

from scipy.sparse import dok_matrix, lil_matrix 
from timeit import timeit 
from collections import defaultdict 

def common_dict(rows, cols): 
    freqs = defaultdict(lambda: defaultdict(int)) 
    for row, col in zip(rows, cols): 
     freqs[row][col] += 1 

    return freqs 

def dok(rows, cols): 
    freqs = dok_matrix((1000,1000)) 
    for row, col in zip(rows, cols): 
     freqs[row,col] += 1 

    return freqs 

def lil(rows, cols): 
    freqs = lil_matrix((1000,1000)) 
    for row, col in zip(rows, cols): 
     freqs[row,col] += 1 

    return freqs 


def benchmark(): 
    cols = range(1000) 
    rows = range(1000) 

    res = timeit("common_dict({},{})".format(rows, cols), 
       "from __main__ import common_dict", 
       number=100) 

    print("common_dict: {}".format(res)) 

    res = timeit("dok({},{})".format(rows, cols), 
       "from __main__ import dok", 
       number=100) 

    print("dok: {}".format(res)) 

    res = timeit("lil({},{})".format(rows, cols), 
       "from __main__ import lil", 
       number=100) 

    print("lil: {}".format(res)) 

Wyniki:

benchmark() 

common_dict: 0.11778324202168733 
dok: 2.2927695910912007 
lil: 1.3541790939634666 

Co to jest, że powoduje takie obciążenie dla modeli macierzy, i czy istnieje jakiś sposób, aby ją przyspieszyć? Czy są przypadki użycia, w których albo dok, albo lil wolą nad powszechnym dyktowaniem dyktów?

Answer 1

Kiedy zmienić += tylko = dla 2 rzadkich tablic:

for row, col in zip(rows, cols): 
    #freqs[row,col] += 1 
    freqs[row,col] = 1 

ich odpowiednie czasy połowę. To, co zajmuje najwięcej czasu, to indeksowanie. Z += musi to być zarówno __getitem__, jak i __setitem__.

Kiedy dokumenty mówią, że dok i lil są lepsze dla iteracyjnej konstrukcji, oznaczają, że łatwiej jest rozszerzyć ich struktury danych niż w przypadku innych formatów.

Kiedy próbuję zrobić csr matrycę z kodem, otrzymuję:

/usr/lib/python2.7/dist-packages/scipy/sparse/compressed.py:690: SparseEfficiencyWarning : Zmiana struktury sparsity csr_matrix jest droga. lil_matrix jest bardziej wydajna. SparseEfficiencyWarning)

i 30 razy mniejsza prędkość.

Tak więc twierdzenia dotyczące prędkości odnoszą się do formatów takich jak csr, a nie do struktur Python lub numpy.

Możesz zajrzeć do kodu Python dla dok_matrix.__get_item__ i dok_matrix.__set_item__, aby zobaczyć, co się stanie, gdy wykonasz freq[r,c].

---

Szybszy sposób skonstruować swoją dok byłoby:

freqs = dok_matrix((1000,1000)) 
d = dict() 
for row, col in zip(rows, cols): 
    d[(row, col)] = 1 
freqs.update(d) 

korzystając z faktu, że dok jest podklasy słownika. Zauważ, że macierz dok nie jest słownikiem słowników. Jego klucze to krotki, takie jak (50,50).

Kolejny szybki sposób konstruowania ten sam rzadki tablicy brzmi:

freqs = sparse.coo_matrix((np.ones(1000,int),(rows,cols))) 

Innymi słowy, skoro masz już tablice (lub zakresów) rows i cols obliczyć odpowiadającą data tablicę, a następnie skonstruować rzadka tablica.

Ale jeśli musisz wykonywać rozrzedzone operacje na macierzy między przyrostowymi krokami wzrostu, wtedy dok lub lil może być twoim najlepszym wyborem.

---

rozrzedzone matricies opracowano liniowych Algebra problemów, takich jak rozwiązanie równania liniowego o dużej macierz rzadką. Używałem ich wiele lat temu w programie MATLAB do rozwiązywania problemów z różnicami skończonymi. Dla tej pracy ostatecznym celem jest format przyjazny dla obliczeń, a format coo był wygodnym formatem inicjowania.

Teraz wiele rzadkich scipy pytań powstaje z scikit-learn i problemów z analizą tekstu. Są również używane w plikach biologicznych baz danych. Jednak metoda definicji (data),(row,col) działa najlepiej.

Tak rzadkie macierze nigdy nie były przeznaczone do szybkiego tworzenia przyrostowego. Tradycyjne struktury w języku Python, takie jak słowniki i listy, są o wiele lepsze.

---

Oto szybciej dok iteracja, że ​​korzysta z jego metod słownikowych. update wydaje się działać tak szybko, jak w zwykłym słowniku. get jest około 3 razy szybsze równoważne indeksowanie (freq[row,col]). Indeksowanie prawdopodobnie używa get, ale musi mieć dużo narzutów.

def fast_dok(rows, cols): 
    freqs = dok_matrix((1000,1000)) 
    for row, col in zip(rows,cols): 
     i = freqs.get((row,col),0) 
     freqs.update({(row,col):i+1}) 
    return freqs 

Pomijanie get, i po prostu robi

  freqs.update({(row,col): 1) 

jest nawet szybciej - szybciej niż defaultdict z defaultdict przykład, i prawie tak szybko, jak proste inicjalizacji słowniku ({(r, c):1 for r,c in zip(rows, cols)})

Answer 2

Istnieje różne powody, dla których twój test nie jest sprawiedliwy. Po pierwsze, uwzględniasz obciążenie związane z budowaniem rzadkich macierzy jako części pętli z timingiem.

Po drugie, i co ważniejsze, należy używać struktur danych, ponieważ są one przeznaczone do użycia, z operacjami na całej tablicy naraz.Oznacza to, że zamiast powtarzać wiersze i kolumny i dodawać po 1 za każdym razem, po prostu dodaj 1 do całej tablicy.