bisect.insort 复杂度未达到预期
bisect.insort complexity not as expected
试图在 python3 中为我必须开发的 frotier 问题找到最佳数据结构，我刚刚意识到使用模块 [=25] 的复杂性=]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.
任何帮助将不胜感激！
二分搜索需要 O(log n) 次比较，但 insort 不仅仅是二分搜索。它还插入元素，将元素插入长度为n的列表需要O(n)时间。
原始代码片段中的 _frontier 命名暗示了某种优先搜索算法。堆可能更有意义，或者来自 sortedcollections.
的 SortedList
您可能错过了 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 元素，你有一个 O(m^2)（二次）解决方案，只需要 O(m log m) 时间使用 TimSort（sorted() 函数使用的排序算法）。
试图在 python3 中为我必须开发的 frotier 问题找到最佳数据结构，我刚刚意识到使用模块 [=25] 的复杂性=]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.
任何帮助将不胜感激！
二分搜索需要 O(log n) 次比较，但 insort 不仅仅是二分搜索。它还插入元素，将元素插入长度为n的列表需要O(n)时间。
原始代码片段中的 _frontier 命名暗示了某种优先搜索算法。堆可能更有意义，或者来自 sortedcollections.
您可能错过了 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 元素，你有一个 O(m^2)（二次）解决方案，只需要 O(m log m) 时间使用 TimSort（sorted() 函数使用的排序算法）。