python - bisect.insort 复杂性不如预期

Question

试图在 python3 中为我必须开发的 frotier 问题找到最佳数据结构，我刚刚意识到使用模块 bisect 来实现一个真正的问题的复杂性按时间排序的插入不是 O(nlog n)，而是呈指数增长。不知道其中的原因，所以想问问你们，以防万一，因为我觉得它真的很有趣。

认为我正确使用了该模块，所以这对我来说应该不是问题，无论如何，这里是用于插入节点对象的代码，它确定通过随机 f 值节点进行的插入。

bisect.insort(self._frontier, (node._f, node))

在几秒钟内得到很多对象，但随着时间的推移不会那么多。 Bakuriu建议我问这个问题，因为他在做了一些测试并得到与我相同的结果后也发现它很有趣。他用来测试的代码如下:

python3 -m timeit -s 'import bisect as B; import random as R;seq=[]' 'for _ in range(100000):B.insort(seq, R.randint(0, 1000000))'

这些是他的结论:

10k insertions is all fine (80ms and up to that point it basically scales linearly [keep in mind that it is O(nlog n) so it's a little bit worse than linear]) but with 100k it takes forever instead of 10 times more. A list of 100k elements isn't really that big and log(100k) is 16 so it's not that big.

任何帮助将不胜感激!

Answer 1

您可能错过了 insort 的时间复杂度是 O(n) 而这是 documented clearly, for bisect.insort_left() :

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

找到插入点很容易，但插入到 Python 列表中则不然，因为超过插入点的元素必须向上移动一步。

另见 TimeComplexity page on the Python Wiki ，其中记录了 list 插入:

Insert O(n)

您可以在 O(log n) 时间内找到插入点，但随后的插入步骤是 O(n)，这使得这种排序方式相当昂贵。

如果您使用它来对 m 元素进行排序，那么对于使用 TimSort(排序sorted() 函数使用的算法。