gpt4 book ai didi

python - bisect.insort函数与list.index和insert函数的速度比较

转载 作者:行者123 更新时间:2023-11-30 22:02:44 27 4
gpt4 key购买 nike

正如Python文档所说,我认为bisect模块比列表内置方法、索引和插入要快得多,以将项目插入到长有序列表中。因此,我只是测量了 bisect_func()insert_func() 这两个函数的时间消耗,如下代码所示。

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

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)

最佳答案

来自 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(log n) 搜索主要由缓慢的 O(n) 插入步骤主导。因此两种方法都是 O(n) 最后,这就是为什么它们的效率相似insort 稍好一些。

关于python - bisect.insort函数与list.index和insert函数的速度比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53735065/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com