bisect.insort的复杂度不如预期

Question

尝试在Python3中寻找最优数据结构以解决一个frontier问题。我刚刚意识到使用模块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个元素很好（80毫秒，到这一点它基本上是线性缩放[请记住它是O(nlog n)，所以比线性差一点])，但插入100k个元素需要很长时间，而不是10倍。100k个元素的列表并不是很大，log(100k)等于16，所以并不是很大。

非常感谢您的帮助！

- jupcan

---

不要计算初始化等内容的时间。使用一个init部分，只需计时插入操作。另外，Python 2还是Python 3？ - Jean-François Fabre

这不是我用的代码，而是另一个用户的代码，我只是进行了压力测试，并意识到在几秒钟内它可以插入近500,000个对象，但在3小时内仅能插入5,000,000个对象，这有点指数级。使用Python3，已更新帖子。 - jupcan

Answer 1

你可能忽略了insort的时间复杂度是O(n)，而这一点在bisect.insort_left()中已经清楚地记录：

请记住，O(log n)搜索被缓慢的O(n)插入步骤所支配。

找到插入点很便宜，但是将元素插入Python列表却不是，因为插入点后面的元素必须向上移动一步。

另请参见Python Wiki上的TimeComplexity页面，其中记录了list插入：

插入 O(n)

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

如果您要对m个元素进行排序，则使用TimSort（sorted()函数使用的排序算法）只需花费O(m log m)的时间，而不是O(m^2)（二次方）的时间。

- Martijn Pieters

---

@jupcan：不会，因为每次附加到列表的时间复杂度是O(1)，总共是O(n)，然后排序的时间复杂度是O(n log n)（如果你的数据已经接近排序，则更低）。这是一个O(n log n)算法。 - Martijn Pieters

术语说明：O(m^2)被认为是多项式，而不是指数。 - user2357112

@jupcan：没错。请注意：如果您不打算使用完整的排序列表，而只是其中的前K个，请考虑使用heapq。 - Martijn Pieters

@user2357112：分心太多，错误太多。换成二次方程式。 - Martijn Pieters

是的，这正是我和@user2357112谈论的内容，我已经尝试过它们，它们比以前更好，但我仍然不知道是否只需要一个顶部元素或所有元素都排序。非常感谢你们的帮助！ - jupcan

Answer 2

Binary search需要进行O(log n)次比较，但是insort不仅仅是二分查找。它还会插入元素，将一个元素插入到长度为n的列表中需要O(n)的时间。

你原始代码片段中的_frontier命名表明了某种优先搜索算法。对于这种情况，使用堆可能更合适，或者使用来自sortedcollections的SortedList。

- user2357112

---

哦，我明白了。我也尝试过使用堆，但问题是我只能在列表的第一个位置得到具有最小属性的对象，但其余元素可能有序也可能无序。 - jupcan

@jupcan：除非您需要在第一个元素之后进行索引访问，否则这不是问题。对于搜索算法中所需的类型的使用，heappop是您需要的所有元素访问方式。 - user2357112

没错，我明白了。使用堆排序算法，我可以在几秒钟内获取近600万个对象...差别很大。问题是我仍然不知道是否需要索引访问，但如果不需要，堆排序将是最好的选择。非常感谢您的帮助 :) - jupcan