bisect.insort函数与list.index和insert函数的速度对比

Question

正如Python文档所说，我认为bisect模块比列表内置方法、索引和插入要快得多，以将项目插入到长有序列表中。因此，我只是测量两个函数

bisect_func()

和

insert_func()

的时间消耗，如下代码所示。

bisect_func()

得分为1.27秒，

insert_func()

得分为1.38秒，这并不是一个巨大的时间差异。我的问题是，在这个例子中我是否错过了一些测试二等分效率的东西？或者二分法不是将项目插入有序列表的唯一有效方法？

import bisect

HAYSTACK = [n for n in range(100000000)]
NEEDLES = [0, 10, 30, 400, 700, 1000, 1100, 2200, 3600, 32000, 999999]

def bisect_func():
    for needle in reversed(NEEDLES):
        bisect.insort(HAYSTACK, needle)

def insert_func():
    for needle in reversed(NEEDLES):
        position = HAYSTACK.index(needle)
        HAYSTACK.insert(position, needle)

if __name__ == '__main__':
    import time
    start = time.time()
    # bisect_func()
    insert_func()
    end = time.time()
    print(end - start)

Answer 1

来自insort的文档：

按排序顺序将 x 插入 a 中。这相当于 a.insert(bisect.bisect_left(a, x, lo, hi), x) 假设 a 是 已经排序了。请记住，O(log n) 搜索主要由 缓慢的 O(n) 插入步骤。

重要的部分是： 请记住，O(log n) 搜索主要由缓慢的 O(n) 插入步骤主导。 因此，两种方法最终都是 O(n)，这就是为什么它们的效率相似，

insort

稍好一些。

Answer 2

二分查找仅提高了查找插入索引的性能。它不会改进列表中的插入，这在两种情况下都是

O(N)

，并且主导了两个函数的渐近复杂性。请记住，插入基于数组的列表需要移动插入索引之后的所有元素。

Answer 3

使用

insort

构建和搜索似乎是

O(N^2)

。为什么？ 每次插入都是

O(N)

，因为插入到

list

需要重新定位/移动插入点之后的所有元素。 有

N

个元素需要插入，每个元素都会产生

O(N)

成本。