bisect.insort函数与list.index函数和插入函数的速度比较

Question

正如Python所说，我认为二分法模块比列表内置方法、索引和插入要快得多，以便将项插入到长顺序列表中。因此，我只需计算这两个函数( bisect_func()和insert_func() )的时间开销，如下所示。

bisect_func()得分1.27s，insert_func()得分1.38s，这不是一个显著的时间差。我的问题是，在这个例子中，我是否遗漏了测试均分效率的东西？还是二分法不是将项目插入有序列表的唯一有效方法？

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

来自乱七八糟的文档

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

重要的部分是:记住O(log n)搜索是由缓慢的O(n)插入步骤主导的。因此，这两种方法最后都是O(n)，这就是它们的效率相似的原因，因为insort稍微好一些。

Answer 2

二进制搜索只提高了查找插入索引的性能。它没有改进列表中的插入，在这两种情况下都是O(N)，并且控制了这两个函数的渐近复杂性。请记住，插入到基于数组的列表中需要在插入索引之后移动所有元素。