heapq的插入比bisect的插入快吗？

Question

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

首先,我将向您展示2个版本的代码,然后询问有关它的问题.

使用bisect的版本:

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.insortO(logn).

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

从bisect.insort文档:

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

按排序顺序插入x.这相当于a.insert(bisect.bisect_left(a,x,lo,hi),x),假设a已经排序.请记住,O(log n)搜索由缓慢的O(n)插入步骤控制.

您可以通过创建一个非常长的列表来测试这个,比如说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).