python – 插入heapq比插入bisect更快吗？

发布时间：2020-12-20 11:07:51 所属栏目：Python 来源：网络整理

导读：我有一个关于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 +

我有一个关于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是一个整数列表

解决方法

你的假设是错误的.既不是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,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(范围(10 ** 8))然后执行l.pop(0)或l.pop()和bisect.insort(1,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).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!