Como otimizar meu cálculo do PageRank?
-
21-09-2019 - |
Pergunta
No livro Inteligência coletiva de programação Encontrei a seguinte função para calcular o PageRank:
def calculatepagerank(self,iterations=20):
# clear out the current PageRank tables
self.con.execute("drop table if exists pagerank")
self.con.execute("create table pagerank(urlid primary key,score)")
self.con.execute("create index prankidx on pagerank(urlid)")
# initialize every url with a PageRank of 1.0
self.con.execute("insert into pagerank select rowid,1.0 from urllist")
self.dbcommit()
for i in range(iterations):
print "Iteration %d" % i
for (urlid,) in self.con.execute("select rowid from urllist"):
pr=0.15
# Loop through all the pages that link to this one
for (linker,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
# Get the PageRank of the linker
linkingpr=self.con.execute("select score from pagerank where urlid=%d" % linker).fetchone()[0]
# Get the total number of links from the linker
linkingcount=self.con.execute("select count(*) from link where fromid=%d" % linker).fetchone()[0]
pr+=0.85*(linkingpr/linkingcount)
self.con.execute("update pagerank set score=%f where urlid=%d" % (pr,urlid))
self.dbcommit()
No entanto, essa função é muito lenta, devido a todas as consultas SQL em todas as iterações
>>> import cProfile
>>> cProfile.run("crawler.calculatepagerank()")
2262510 function calls in 136.006 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 136.006 136.006 <string>:1(<module>)
1 20.826 20.826 136.006 136.006 searchengine.py:179(calculatepagerank)
21 0.000 0.000 0.528 0.025 searchengine.py:27(dbcommit)
21 0.528 0.025 0.528 0.025 {method 'commit' of 'sqlite3.Connecti
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler
1339864 112.602 0.000 112.602 0.000 {method 'execute' of 'sqlite3.Connec
922600 2.050 0.000 2.050 0.000 {method 'fetchone' of 'sqlite3.Cursor'
1 0.000 0.000 0.000 0.000 {range}
Então eu otimizei a função e criei isso:
def calculatepagerank2(self,iterations=20):
# clear out the current PageRank tables
self.con.execute("drop table if exists pagerank")
self.con.execute("create table pagerank(urlid primary key,score)")
self.con.execute("create index prankidx on pagerank(urlid)")
# initialize every url with a PageRank of 1.0
self.con.execute("insert into pagerank select rowid,1.0 from urllist")
self.dbcommit()
inlinks={}
numoutlinks={}
pagerank={}
for (urlid,) in self.con.execute("select rowid from urllist"):
inlinks[urlid]=[]
numoutlinks[urlid]=0
# Initialize pagerank vector with 1.0
pagerank[urlid]=1.0
# Loop through all the pages that link to this one
for (inlink,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
inlinks[urlid].append(inlink)
# get number of outgoing links from a page
numoutlinks[urlid]=self.con.execute("select count(*) from link where fromid=%d" % urlid).fetchone()[0]
for i in range(iterations):
print "Iteration %d" % i
for urlid in pagerank:
pr=0.15
for link in inlinks[urlid]:
linkpr=pagerank[link]
linkcount=numoutlinks[link]
pr+=0.85*(linkpr/linkcount)
pagerank[urlid]=pr
for urlid in pagerank:
self.con.execute("update pagerank set score=%f where urlid=%d" % (pagerank[urlid],urlid))
self.dbcommit()
Esta função é muitas vezes mais rápida (mas usa muito mais memória para todos os dicionários temporários) porque evita as consultas SQL desnecessárias em todas as iterações:
>>> cProfile.run("crawler.calculatepagerank2()")
90070 function calls in 3.527 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.004 0.004 3.527 3.527 <string>:1(<module>)
1 1.154 1.154 3.523 3.523 searchengine.py:207(calculatepagerank2
2 0.000 0.000 0.058 0.029 searchengine.py:27(dbcommit)
23065 0.013 0.000 0.013 0.000 {method 'append' of 'list' objects}
2 0.058 0.029 0.058 0.029 {method 'commit' of 'sqlite3.Connectio
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler
43932 2.261 0.000 2.261 0.000 {method 'execute' of 'sqlite3.Connecti
23065 0.037 0.000 0.037 0.000 {method 'fetchone' of 'sqlite3.Cursor'
1 0.000 0.000 0.000 0.000 {range}
Mas é possível reduzir ainda mais o número de consultas SQL para acelerar ainda mais a função?Atualizar: Indentação fixa no CalcularPagerank2 ().
Solução 4
Estou respondendo à minha própria pergunta, já que, no final, saiu que uma mistura de todas as respostas funcionou melhor para mim:
def calculatepagerank4(self,iterations=20):
# clear out the current PageRank tables
self.con.execute("drop table if exists pagerank")
self.con.execute("create table pagerank(urlid primary key,score)")
self.con.execute("create index prankidx on pagerank(urlid)")
# initialize every url with a PageRank of 1.0
self.con.execute("insert into pagerank select rowid,1.0 from urllist")
self.dbcommit()
inlinks={}
numoutlinks={}
pagerank={}
for (urlid,) in self.con.execute("select rowid from urllist"):
inlinks[urlid]=[]
numoutlinks[urlid]=0
# Initialize pagerank vector with 1.0
pagerank[urlid]=1.0
for src,dest in self.con.execute("select distinct fromid, toid from link"):
inlinks[dest].append(src)
numoutlinks[src]+=1
for i in range(iterations):
print "Iteration %d" % i
for urlid in pagerank:
pr=0.15
for link in inlinks[urlid]:
linkpr=pagerank[link]
linkcount=numoutlinks[link]
pr+=0.85*(linkpr/linkcount)
pagerank[urlid]=pr
args=((pagerank[urlid],urlid) for urlid in pagerank)
self.con.executemany("update pagerank set score=? where urlid=?" , args)
self.dbcommit()
Então eu substituí os dois primeiros loops, conforme sugerido por allyourcode
, mas além disso, também usou executemany () como na solução de ˜unutbu
. Mas diferente ˜unutbu
Eu uso uma expressão de gerador para args, para não desperdiçar muita memória, embora o uso de uma compreensão da lista tenha sido um pouco mais rápido. No final, a rotina foi 100 vezes mais rápida que a rotina sugerida no livro:
>>> cProfile.run("crawler.calculatepagerank4()")
33512 function calls in 1.377 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.004 0.004 1.377 1.377 <string>:1(<module>)
2 0.000 0.000 0.073 0.036 searchengine.py:27(dbcommit)
1 0.693 0.693 1.373 1.373 searchengine.py:286(calculatepagerank4
10432 0.011 0.000 0.011 0.000 searchengine.py:321(<genexpr>)
23065 0.009 0.000 0.009 0.000 {method 'append' of 'list' objects}
2 0.073 0.036 0.073 0.036 {method 'commit' of 'sqlite3.Connectio
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler
6 0.379 0.063 0.379 0.063 {method 'execute' of 'sqlite3.Connecti
1 0.209 0.209 0.220 0.220 {method 'executemany' of 'sqlite3.Conn
1 0.000 0.000 0.000 0.000 {range}
Deve -se também estar ciente dos seguintes problemas:
- Se você usar a formação de string com
%f
Em vez de usar um espaço reservado?
Para construir a instrução SQL, você perderá precisão (por exemplo, eu tenho 2.9796095721920315 usando?
mas 2.9796100000000001 Usando%f
. - Os links duplicados de uma página para outra são tratados como apenas um link no algoritmo PageRank padrão. No entanto, a solução do livro não levou isso em consideração.
- Todo o algoritmo do livro é falho: o motivo é que, em cada iteração, a pontuação do PageRank não é armazenada em uma segunda tabela. Mas isso significa que o resultado de uma iteração depende da ordem das páginas percorridas e isso pode mudar o resultado após várias iterações drasticamente. Para corrigir esse problema, ou precisa usar uma tabela/dicionário adicional para armazenar o PageRank para a próxima iteração ou usar um algoritmo completamente diferente como Iteração de energia.
Outras dicas
Se você possui um banco de dados muito grande (por exemplo, registros ~ # páginas no www) usando o banco de dados de maneira semelhante ao que é sugerido no livro faz sentido, porque você não será capaz de manter todos esses dados na memória .
Se o seu conjunto de dados for pequeno o suficiente, você poderá (provavelmente) melhorar sua segunda versão por não fazer tantas consultas. Tente substituir seu primeiro loop por algo assim:
for urlid, in self.con.execute('select rowid from urllist'):
inlinks[urlid] = []
numoutlinks[urlid] = 0
pagerank[urlid] = 1.0
for src, dest in self.con.execute('select fromid, toid from link'):
inlinks[dest].append(src)
numoutlinks[src] += 1
Esta versão faz exatamente 2 consultas em vez de consultas O (n^2).
Acredito que a maior parte do tempo está sendo gasta nessas consultas SQL:
for (urlid,) in self.con.execute("select rowid from urllist"):
...
for (inlink,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
...
numoutlinks[urlid]=self.con.execute("select count(*) from link where fromid=%d" % urlid).fetchone()[0]
Supondo que você tenha memória suficiente, você pode reduzir isso para apenas duas consultas:
SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)
eSELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid
Então você pode percorrer os resultados e construir inlinks
, numoutlinks
e pagerank
.
Você também pode se beneficiar do uso collections.defaultdict
:
import collections
import itertools
def constant_factory(value):
return itertools.repeat(value).next
O seguinte faz então inlinks
um ditado de conjuntos. Conjuntos são apropriados, pois você só deseja URLs distintos
inlinks=collections.defaultdict(set)
E isso faz pagerank
Um ditado cujo valor padrão é 1.0:
pagerank=collections.defaultdict(constant_factory(1.0))
A vantagem de usar coleções.DefaultDict é que você não precisa pré-inicializar os ditos.
Então, junte, o que estou sugerindo seria algo assim:
import collections
def constant_factory(value):
return itertools.repeat(value).next
def calculatepagerank2(self,iterations=20):
# clear out the current PageRank tables
self.con.execute("DROP TABLE IF EXISTS pagerank")
self.con.execute("CREATE TABLE pagerank(urlid primary key,score)")
self.con.execute("CREATE INDEX prankidx ON pagerank(urlid)")
# initialize every url with a PageRank of 1.0
self.con.execute("INSERT INTO pagerank SELECT rowid,1.0 FROM urllist")
self.dbcommit()
inlinks=collections.defaultdict(set)
sql='''SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)'''
for f,t in self.con.execute(sql):
inlinks[t].add(f)
numoutlinks={}
sql='''SELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid'''
for f,c in self.con.execute(sql):
numoutlinks[f]=c
pagerank=collections.defaultdict(constant_factory(1.0))
for i in range(iterations):
print "Iteration %d" % i
for urlid in inlinks:
pr=0.15
for link in inlinks[urlid]:
linkpr=pagerank[link]
linkcount=numoutlinks[link]
pr+=0.85*(linkpr/linkcount)
pagerank[urlid]=pr
sql="UPDATE pagerank SET score=? WHERE urlid=?"
args=((pagerank[urlid],urlid) for urlid in pagerank)
self.con.executemany(sql, args)
self.dbcommit()
Você tem carneiro suficiente para segurar a matriz esparsa (fromid, toid)
de alguma forma? Isso permitiria grandes otimizações (com grandes alterações algorítmicas). Pelo menos, cache na memória o (fromid, numlinks)
que você agora faz com um select count(*)
em seu loop mais íntimo deve ajudar (eu imagino este cache, sendo O(N)
no espaço se você estiver lidando com N
URLs, seria mais provável que se encaixasse na memória).