如何优化我的PageRank计算?

如果您的数据集足够小,您可以(可能)通过不执行太多查询来改进第二个版本。尝试用以下内容替换第一个循环:

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

这个版本只执行2个查询,而不是O(n^2)个查询。

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]            

假设您有足够的内存,您可以将其减少为两个查询:

1. SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)
   和
2. SELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid

然后你就可以循环浏览结果并构建 inlinks , numoutlinks 和 pagerank

你也可以从使用 collections.defaultdict

import collections
import itertools
def constant_factory(value):
    return itertools.repeat(value).next

下面是 链接 一套格言。因为 您只需要不同的URL

inlinks=collections.defaultdict(set)

页面排名

pagerank=collections.defaultdict(constant_factory(1.0))

使用collections.defaultdict的优点是 不需要预先初始化dicts。

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()

你有足够的内存来容纳稀疏矩阵吗 (fromid, toid) 以某种形式?这将允许大的优化(大的算法变化)。至少,在内存中缓存 (fromid, numlinks) select count(*) 那个 O(N) 在太空中,如果你在处理 N

我在回答我自己的问题,因为最终发现,所有答案的混合对我最有效:

    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() 

所以我按照 allyourcode ˜unutbu 联合国大学 我为args使用了一个生成器表达式,以避免浪费太多内存,尽管使用列表理解要快一点。最后,这套套路比书中建议的套路快了100倍:

>>> 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}

还应注意以下问题:

1. 如果使用字符串格式化 %f 而不是使用占位符 ? 对于构造SQL语句,您将失去精度(例如,我使用 ? 但29796100000001使用 .
2. 在默认PageRank算法中,从一个页面到另一个页面的重复链接仅被视为一个链接。然而,书中的解决方案没有考虑到这一点。
3. 书中的整个算法都有缺陷:原因是,在每次迭代中,pagerank得分都没有存储在第二个表中。但这意味着一次迭代的结果取决于循环页面的顺序,这可能会在几次迭代后极大地改变结果。要解决这个问题,要么使用一个额外的表/字典来存储pagerank以便下一次迭代,要么使用一个完全不同的算法,比如 Power Iteration .