遍历堆化列表

Question

我正在进行蒙特卡罗模拟.作为此任务的一部分,我生成均匀分布在一个区间内的样本(0,100).

generate = lambda: uniform(0,100)

当所有最接近的生成点对满足条件时,迭代停止.

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

我需要有一些结构来有效地保留所有生成的点,并能够按升序遍历它们以check在所有后续对上执行.

heapqPython中有一个模块支持非常有效的堆结构.我决定使用它.

我遇到了一个问题.我发现此模块不支持遍历过程.我发现以升序访问堆的值的唯一方法是使用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

我会在堆上使用list.sort().这使得堆条件保持不变,并且可以直接迭代底层列表.

FWIW,在Timsort使用的算法list.sort将已经存在堆中部分排序的优势.