python - heapq 的插入是否比 bisect 的插入快？

Question

我有一个关于 bisect 和 heapq 的问题。

首先，我将向您展示 2 个版本的代码，然后提出有关它的问题。

使用二分法的版本:

while len(scoville) > 1:
    a = scoville.pop(0)
    #pops out smallest unit
    if a >= K:
        break
    b = scoville.pop(0)
    #pops out smallest unit
    c = a + b * 2
    bisect.insort(scoville, c)

使用heapq的版本

while len(scoville) > 1:
    a = heapq.heappop(scoville)
    #pops out smallest unit
    if a >= K:
        break
    b = heapq.heappop(scoville)
    #pops out smallest unit
    c = a + b * 2
    heapq.heappush(scoville, c)

两种算法都使用 2 次弹出和 1 次插入。

据我所知，在使用bisect的版本中，list的弹出操作是O(1)，bisect类的插入操作是O(logn)。

而在使用heapq的版本中，堆的弹出操作平均为O(1)，堆的插入操作平均为O(logn)。

所以这两个代码应该具有大致相同的时间效率。但是，使用 bisect 的版本在某些代码挑战站点上一直未能通过时间效率测试。

有人猜对了吗？

*scoville 是一个整数列表

Answer 1

你的假设是错误的。 pop(0) O(1) 和 bisect.insort O(logn) 都不是。

问题在于，在这两种情况下，弹出或插入元素之后的所有元素都必须向左或可能向左移动一个位置，这使得这两种操作都为 O(n)。

来自bisect.insort文档:

bisect.insort_left(a, x, lo=0, hi=len(a))

Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

你可以通过创建一个很长的列表来测试它，比如说 l = list(range(10**8)) 然后做 l.pop(0)或 l.pop() 和 bisect.insort(l, 0) 或 bisect.insort(l, 10**9)。最后的弹出和插入操作应该是瞬时的，而其他操作有短暂但明显的延迟。您还可以使用 %timeit 在较短的列表上重复测试它，如果您交替弹出和插入，以便列表的长度在数千次运行中保持不变:

>>> l = list(range(10**6))
>>> %timeit l.pop(); bisect.insort(l, 10**6)
100000 loops, best of 3: 2.21 us per loop
>>> %timeit l.pop(0); bisect.insort(l, 0)
100 loops, best of 3: 14.2 ms per loop

因此，使用bisect的版本是O(n)，使用heapq的版本是O(logn)。