Comment optimiser mon calcul du PageRank?
https://stackoverflow.com/questions/2484445
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Dans le livre Programmation Intelligence collective j'ai trouvé la fonction suivante pour calculer le 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()
Cependant, cette fonction est très lent, à cause de toutes les requêtes SQL dans chaque itération
>>> 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}
J'optimisé la fonction et est venu avec ceci:
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()
Cette fonction est plusieurs fois plus rapide (mais utilise beaucoup plus de mémoire pour tous les dictionnaires temporaires) car elle évite les requêtes inutiles SQL dans chaque itération:
>>> 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}
Mais est-il possible de réduire encore le nombre de requêtes SQL pour accélérer encore plus la fonction? Mise à jour :. Indentation fixe dans calculatepagerank2 ()
La solution 4
Je réponds à ma propre question, car à la fin il est sorti qu'un mélange de toutes les réponses qui fonctionne le mieux pour moi:
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()
Je remplacé les deux premières boucles comme suggéré par allyourcode, mais en plus également utilisé executemany () comme dans la solution de ˜unutbu. Mais contrairement à ˜unutbu utiliser une expression de générateur pour args, de ne pas perdre trop de mémoire, bien que l'utilisation d'une compréhension de la liste était un peu plus rapide. En fin de la routine était 100 fois plus rapide que la routine suggérée dans le livre:
>>> 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}
Il faut aussi être conscient des problèmes suivants:
- Si vous utilisez la chaîne avec formating
%fau lieu d'utiliser un espace réservé pour?de construire l'instruction SQL, vous perdrez la précision (par exemple je me suis 2,9796095721920315 en utilisant?mais 2,9796100000000001 en utilisant%f. - liens en double d'une page à l'autre sont traités comme un seul lien dans l'algorithme de PageRank par défaut. Cependant, la solution du livre n'a pas pris cela en compte.
- L'algorithme entier du livre est défectueux: La raison en est que, dans chaque itération, le score pagerank ne sont pas stockées dans une seconde table. Mais cela signifie que le résultat d'une itération dépend de l'ordre des pages bouclées et cela peut changer le résultat après plusieurs itérations de façon assez radicale. Pour résoudre ce problème, il doit soit utiliser une table / dictionnaire supplémentaire pour stocker le pagerank pour la prochaine itération ou d'utiliser un algorithme complètement différent comme Puissance Iteration.
Autres conseils
Si vous avez une base de données très importante (par exemple # records ~ # pages du WWW) en utilisant la base de données de manière similaire à ce qui est suggéré dans le livre est logique, parce que vous n'êtes pas allez être en mesure de garder tout ce que les données dans la mémoire.
Si votre ensemble de données est assez petit, vous pouvez (probablement) à améliorer votre deuxième version en ne faisant pas tant de requêtes. Essayez de remplacer votre première boucle avec quelque chose comme ceci:
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
Cette version fait exactement 2 requêtes au lieu de requêtes O (n ^ 2).
Je crois que la plupart du temps est consacré à ces requêtes 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]
En supposant que vous avez suffisamment de mémoire, vous pouvez être en mesure de réduire ce nombre à deux requêtes:
-
SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)
et -
SELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid
boucle Ensuite, vous pouvez à travers les résultats et construire inlinks, numoutlinks et pagerank.
Vous pouvez également bénéficier de l'utilisation collections.defaultdict :
import collections
import itertools
def constant_factory(value):
return itertools.repeat(value).next
Ce qui suit fait alors inlinks un dict de jeux. Les ensembles sont appropriés depuis
vous ne souhaitez que urls distincts
inlinks=collections.defaultdict(set)
Et cela fait pagerank un dict dont la valeur par défaut est 1.0:
pagerank=collections.defaultdict(constant_factory(1.0))
L'avantage d'utiliser collections.defaultdict est que vous ne pas besoin d'effectuer une pré-initialiser les dicts.
Alors, mettez ensemble, ce que je suggère ressemblerait à quelque chose comme ceci:
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()
Avez-vous suffisamment de RAM pour maintenir la matrice clairsemée (fromid, toid) sous une certaine forme? Cela permettrait à de grandes optimisations (avec de grands changements algorithmiques). Au moins, la mise en cache en mémoire le (fromid, numlinks) que vous faites maintenant avec un select count(*) dans votre boucle interne devrait aider (j'imagine que cache, étant O(N) dans l'espace si vous avez affaire à des URL de N, serait être plus susceptibles de se tenir dans la mémoire).
