速度比较平分功能和列表.索引和插入函数

Question

正如Python-doc所说，我认为bisect模块比list内置方法、index和insert要快得多。因此，我只需测量这两个函数的时间开销，bisect_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

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

Answer 2

根据insort的文档：

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.

重要的部分是：记住O（logn）搜索是由缓慢的O（n）插入步骤控制的。所以这两种方法最后都是O（n），这就是为什么它们的效率相似，其中{}稍好一些。在