遍历堆化列表

Question

我正在做一个蒙特卡洛模拟。在这个任务中，我需要在一个区间内均匀生成样本，区间是(0,100)。

generate = lambda: uniform(0,100)

当所有生成的点对都符合条件时，迭代就会停止。

check = lambda a,b: True if (b-a)<5 else False

我需要一种结构来有效地保存所有生成的点，并能够按升序遍历它们，以便对所有后续的点对进行check操作。

Python中有一个heapq模块，它支持一种非常有效的堆结构。我决定使用它。

但我遇到了一个问题。我没有找到这个模块支持的遍历方法。唯一能以升序访问堆中值的方式是使用heapq.heappop，但这会从堆中删除值。

我找到了一种解决方法，就是把堆对象复制到一个新的堆中，然后在新的堆上使用heappop进行迭代。但我觉得每次迭代都复制整个结构到内存中并不是很有效。

有没有其他更有效的方法来实现我想做的事情呢？

---

下面是简化的代码示例。

import heapq
from random import uniform
from itertools import tee, izip, count
from copy import copy


def pairwise(iterable): #get values from iterator in pairs
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)


check = lambda a,b: True if (b-a)<5 else False
generate = lambda: uniform(0,100)


def iterate_heap(heap):
    heap = copy(heap) #Here I have to copy the heap to be able to traverse
    try:
        while True:
            yield heapq.heappop(heap)
    except IndexError:
        return


def trial():
    items = []

    for i in count():
        item = generate()
        heapq.heappush(items, item)

        it = iterate_heap(items)
        it = pairwise(it)

        if i>0 and all(check(a,b) for a,b in it): #if i==0 then 'it' returns no values and 'all' returns True
            return i

print "The solution is reached. It took %d iterations." % trial()

paiwise函数来自这里的一个示例。

---

更新： 在这个使用heappop的实现中，每次迭代的复杂度是O(n*log(n))：

复制堆的复杂度：O(n)

向堆中添加新值的复杂度：O(log(n))

遍历：n个元素 * 从堆中弹出每个值的复杂度O(log(n)) -> O(n*log(n))。

结果：O(n+log(n)+n*log(n)) = O(n*log(n))

但我希望遍历的复杂度是O(n)，这样最终的复杂度就是O(n)。

顺便说一下，如果我们使用简单的排序列表，每次添加时都需要对列表进行排序，所以复杂度是O(n*log(n))，但遍历的复杂度是n*O(1) -> O(n)。所以，最终的复杂度仍然是O(n*log(n))。

我找到了一种解决方案，就是使用bisect模块。找到插入位置的复杂度是O(log(n))。向列表中添加的复杂度是O(n)（因为插入后，所有后面的值都需要移动）。遍历的复杂度是O(n)。所以，最终的复杂度是O(n)。

不过，我还是想知道，是否有办法在Python中使用堆来解决这个任务。

Answer 1

我做了一些效率计算。

使用bisect模块时，性能最好：在我的电脑上，往列表中间插入10000个元素只花了0.037秒（Python 2.7）。

使用sortedlist这个来自blist模块的工具，插入同样数量的元素花了0.287秒。

而用传统的list，每次添加元素后都要用sort进行排序，结果花了2.796秒。（现在Python使用的是算法，号称在几乎已排序的列表上效率很高；但结果显示，使用bisect的效率还是更好。）

---

我用来进行这些计算的代码：

import bisect
import timeit
import __main__
import blist

N = 10000 #Number of executions
L = 1000 #Length of initial list

def test_f_bisect(a):
    bisect.insort_right(a,500)


def test_f_list_sort(a):
    a.append(500)
    a.sort()


test_f_blist_init = '''
from __main__ import test_f_blist
import blist
a = blist.sortedlist(range({L}))
'''.format(L=L)
def test_f_blist(a):
    a.add(500)


names = dir(__main__)
for name in names:
    attr = getattr(__main__,name)
    if hasattr(attr,'__call__'):
        if name.startswith('test_f_'):
            init_name = name + '_init'
            if hasattr(__main__, init_name):
                init = getattr(__main__,init_name)
            else:
                init = 'from __main__ import {name}; a = list(range({L}))'.format(name=name, L=L)
            t = timeit.Timer(stmt='{name}(a)'.format(name=name),
                             setup=init)

            time = t.timeit(N)
            print('{name}: {time}'.format(name=name,time=time))

Answer 2

来自Python文档：

这两点让你可以把堆当作普通的Python列表来看，没什么意外：heap[0]是最小的元素，而heap.sort()可以保持堆的特性！

那为什么不能把堆直接当成列表来遍历呢？

Answer 3

我会在堆上使用 list.sort()。这样可以保持堆的结构不变，并且可以直接遍历底层的列表。

顺便提一下，Timsort 算法是 list.sort 使用的，它会利用堆中已经存在的部分排序。