Page Rank w Pythonie

Question

Jestem nowy w Pythonie, a ja staram się obliczyć Page Rank wektor według tego równania w Pythonie:

Gdzie Pi (k) jest Page-Rank wektor po k-tej iteracji, G macierz pomocną, H Hiperlink macierzy jest zwisające wektor węzeł alfa = 0,85 e jest wektorem jedynek.

obliczeń z G zajmuje dużo czasu, z wykorzystaniem macierzy hiperłącze H, czyli macierz rzadką, powinno znacznie mniej czasu.

Oto mój kod:

for i in range(1, k_steps+1): 
    for j in range(0, len(dictionary_urls)): 
    for k in range(0, len(dictionary_urls)): 
     if matrix_H[k][j] != 0: 
      matrix_pi_k[i][j] += matrix_pi_k[i-1][k] * float(matrix_H[k][j]) 
     alpha_pi_k_a += matrix_pi_k[i-1][k]*float(vector_a[k]) 

    alpha_pi_k_a = alpha_pi_k_a * float(alpha) 
    alpha_pi_k_a = alpha_pi_k_a + float((1- alpha)) 
    alpha_pi_k_a = alpha_pi_k_a/float(len(dictionary_urls)) 
    matrix_pi_k[i][j] = matrix_pi_k[i][j] * float(alpha) 

    matrix_pi_k[i][j] = matrix_pi_k[i][j] + float(alpha_pi_k_a) 
    alpha_pi_k_a = 0 

k_steps jest liczba iteracji potrzebne.

dictionary_links zawiera wszystkie adresy URL.

Po wykonaniu kodu matrix_pi_k powinny mieć wszystkie nosiciela PI

I oblicza wszystkie zmienne, które potrzebne. Mam czas działania przy użyciu macierzy H jest prawie równa czas pracy przy użyciu matrycy G, choć teoretycznie powinno być inaczej.

Dlaczego? A co powinienem zmienić, aby skrócić czas działania?

Dziękuję.

Answer 1

Problem polega na tym, że mnożysz rzadką macierz przez gęsty wektor, używając tego samego starego algorytmu mnożenia gęstej macierzy-wektora. W ten sposób nie zauważysz żadnych przyspieszeń.

Załóżmy, że masz macierz nxnA (gęsta lub rzadka) i n -wektor x. Aby obliczyć y = Ax, możemy napisać:

y = [0]*n 
for i in range(n): 
    for j in range(n): 
     y[i] += A[i,j]*x[j] 

Działa to czy matryca A jest gęsta lub rzadka. Załóżmy jednak, że A jest rzadki. Nadal mamy pętlę ponad wszystkich kolumn z A, aby obliczyć pojedynczy wpis z y, mimo że większość wpisów będzie równa zero. Tak więc zewnętrzna pętla przechodzi przez iteracje n, a wewnętrzna pętla przechodzi również przez iteracje n.

Jeśli mamy znać, które wpisy A są niezerowe, możemy zrobić znacznie lepiej. Załóżmy, że mamy listę wszystkich niezerowych pozycji wiersza i, nazywamy to nonzero[i]. Wtedy możemy wymienić wewnętrzną pętlę z iteracji na tej liście:

y = [0]*n 
for i in range(n): 
    for j in nonzero[i]: 
     y[i] += A[i,j]*x[j] 

Więc gdy nasza zewnętrzna pętla robi n iteracji, wewnętrzna pętla robi tylko tyle powtórzeń ile jest niezerowe wpisy.

Tutaj następuje przyspieszenie z rzadkim mnożeniem wektorów macierzy.

Użyj numpy!

Ale masz inny problem: próbujesz wykonać mnożenie macierzy za pomocą czystego Pythona, który (ze względu na sprawdzanie typu, nieciągłe struktury danych itp.) Jest wolny wolny. Rozwiązaniem jest użycie numpy, która zapewnia szybkie algorytmy i struktury danych. Wtedy możesz użyć scipy's sparse matrices, ponieważ zaimplementują dla ciebie szybkie rozrzedzenie wektorów macierzy-wektora.

Eksperyment

Możemy pokazać to wszystko za pomocą szybkiego eksperymentu. Najpierw będziemy generować 10,000 x 10,000 gęstą matrycę A:

>>> import numpy as np 
>>> n = 10000 
>>> A = np.random.sample((n,n)) 

Potem zrobimy rzadki macierzy B o wartości odcięcia A. B ma taki sam rozmiar jak A, ale tylko 10% jej zapisów są niezerowe:

>>> B = np.where(A < .1, A, 0).astype(float) 

Teraz zrobimy gęstą wektor pomnożyć A i B z:

>>> x = np.random.sample(n) 
>>> %timeit A.dot(x) 
10 loops, best of 3: 46.7 ms per loop 
>>> %timeit B.dot(x) 
10 loops, best of 3: 43.7 ms per loop 

przybiera tyle samo czasu, aby obliczyć Ax, tak jak ma to na celu obliczenie Bx, mimo że B jest "rzadki". Oczywiście nie jest to rzadkie: jest przechowywane jako gęstą matrycę z wieloma wejściami zerowymi.Zróbmy to rzadko:

>>> sparse_B = scipy.sparse.csr_matrix(B) 
>>> 100 loops, best of 3: 12 ms per loop 

Jest nasz przyśpieszenie! Teraz, dla zabawy, co jeśli przechowujemy A jako rzadką matrycę, mimo że jest naprawdę gęsta?

>>> sparse_A = scipy.sparse.csr_matrix(A) 
>>> %timeit sparse_A.dot(x) 
10 loops, best of 3: 112 ms per loop 

Ouch! Ale należy się tego spodziewać, ponieważ przechowywanie A jako rzadkiej matrycy spowoduje pewne obciążenie podczas mnożenia.

Answer 2

podstawie formuły, obliczenie macierzy H nie wygląda szybciej niż w przypadku matrycy G.

Objaśnienie:

Czasami warto spojrzeć na introduction to Big O notation.

Prawa część (po +) w formule składa się tylko z prostych obliczeń bez pętli, a notacja Big O to tylko O(1). Co oznacza, że ​​nie zależy od liczby adresów URL, które bierzesz pod uwagę.

Podczas, gdy obliczenia dla H i G wydają się być co najmniej O(n^2) (n jest liczbą adresów URL).

Edit:

W głębokim zagnieżdżonych części kodu, masz dwie instrukcje, jeden z nich jest uzależnione od tego, czy matrix_H[k][j] wynosi 0 lub nie. Nadal, jeśli jest to 0, co będzie miało miejsce w większości przypadków, jeśli H jest macierzą rzadką, druga instrukcja zostanie wykonana. Dodatkowo, mimo wszystko wchodzisz w pętlę.

To nadal daje złożoność O(n^2), więc parsowanie H nie jest (dużo) szybsze niż analizowanie G.