提高heapq效率

Question

所以我发现自己在利用heapq进行一些计算。但是，对于我正在处理的问题，它运行缓慢，因为堆变得非常大。在

我以为我可以选择加快速度。与其制造一个巨大的堆，不如把它变成一堆堆。但是，令我惊讶的是，“更高效”的代码明显较慢。在更高效的代码中会有更多的开销，但我真的认为它会赢很多。在分解了这个问题之后，我有两个函数，它们执行相同的网络计算。f1是“幼稚”（而且速度更快）的版本。f2是“改进”（但速度较慢）的版本。我在这两种方法中都做了一些随机数的生成，但是我使用的是同一种子，所以这确实是一回事。在

import random
import heapq
def f1():
    random.seed(1)
    Q=[0]
    while Q:
        value = heapq.heappop(Q)
        #print value
        if value<0.5:
            for counter in range(16):
                heapq.heappush(Q,value + 0.1 + (random.random()/1000))
    print value

def f2():
    random.seed(1)
    Q=[[0]]
    while Q:
        subQ = heapq.heappop(Q)
        value = heapq.heappop(subQ)
        #print value
        if subQ:
            heapq.heappush(Q,subQ)
        newQ = []
        if value<0.5:
            for counter in range(16):
                newQ.append(value + 0.1 + (random.random()/1000))
            heapq.heapify(newQ)
            heapq.heappush(Q,newQ)
    print value

为什么堆（f2）的运行速度明显较慢？它应该调用heappush相同的次数，heappop应该是原来的两倍。但是堆的大小应该要小得多，所以我希望它运行得更快。在

Answer 1

所以我只是没有把代码推得足够紧。这里有一些修改过的代码。当subQ变得非常大时，我追求的利益就会显现出来。在

def f1(m,n):
    random.seed(1)
    Q=[0]
    for counter in range(m):
        value = heapq.heappop(Q)
        #print value
        for newcounter in range(n):
            heapq.heappush(Q,random.random())
    print value #should be the same for both methods, so this is just a test

def f2(m,n):
    random.seed(1)
    Q=[[0]]
    for counter in range(1000000):
        subQ = heapq.heappop(Q)
        value = heapq.heappop(subQ)
        #print value
        if subQ:
            heapq.heappush(Q,subQ)
        newQ = []
        for newcounter in range(n):
            newQ.append(random.random())
        heapq.heapify(newQ)
        heapq.heappush(Q,newQ)
    print value #should be the same for both methods, so this is just a test

当我分析f1(1000000,10)和f2(1000000,10)时，我得到的运行时间是10.7秒和14.8秒。相关细节如下：

一楼：

ncalls tottime percall cumtime percall filename:lineno(function)

1000000 1.793 0.000 1.793 0.000 {_heapq.heappop}

10000000 3.856 0.000 3.856 0.000 {_heapq.heappush}

二楼：

1000000 1.095 0.000 1.095 0.000 {_heapq.heapify}

2000000 2.628 0.000 2.628 0.000 {_heapq.heappop}

1999999 2.245 0.000 2.245 0.000 {_heapq.heappush}

10000000 1.114 0.000 1.114 0.000 {method 'append' of 'list' objects}

因此，net f2由于额外的heappop，以及heapify和{}而损失。它在heappush上做得更好。在

但是当我用一个更大的内部循环来挑战它并运行f1(1000,100000)和{}时，我们得到

一楼：

1000 0.015 0.000 0.015 0.000 {_heapq.heappop}

100000000 28.730 0.000 28.730 0.000 {_heapq.heappush}

二楼：

1000 19.952 0.020 19.952 0.020 {_heapq.heapify}

2000 0.011 0.000 0.011 0.000 {_heapq.heappop}

1999 0.006 0.000 0.006 0.000 {_heapq.heappush}

100000000 6.977 0.000 6.977 0.000 {method 'append' of 'list' objects}

所以我们现在在heappush上做得更好，现在{}运行得更快就足够了（69秒对75秒）。在

所以我发现我只是没有把我的代码推得足够紧。我需要的东西变得足够大，以至于许多调用heappush的速度比许多调用heapify慢。在