为什么二分查找比排序慢？

Question

我知道bisect使用二分查找来保持列表排序。然而，我做了一个计时测试，发现读取和排序值的方式胜过于我的认知。请更有经验的用户解释一下这种行为。以下是我用来测试时间的代码。

import timeit

setup = """
import random
import bisect
a = range(100000)
random.shuffle(a)
"""

p1 = """
b = []
for i in a:
    b.append(i)
b.sort()
"""

p2 = """
b = []
for i in a:
    bisect.insort(b, i)
"""

print timeit.timeit(p1, setup=setup, number = 1)
print timeit.timeit(p2, setup=setup, number = 1)

# 0.0593081859178
# 1.69218442959
# Huge difference ! 35x faster.

在第一个过程中，我逐个取值而不是仅仅排序a以获取类似文件读取的行为。这比二分查找快得多。

- Max Paython

---

因为timsort是一种高效的排序算法，而列表插入操作较慢。 - jonrsharpe

什么意思？如果您已经有一个排序好的列表，并且想要保持它的排序，那是最好的方法。而且许多其他操作在排序列表上更有效率。 - jonrsharpe

bisect是用于在列表中频繁进行搜索而不是添加项目时使用的工具。 - chepner

有道理，因此二分法对于从头开始排序列表没有用处，就像插入排序一样慢。 - Max Paython

那就是插入排序。 - jonrsharpe

Answer 1

• 对列表进行排序需要大约 O(N*log(N)) 的时间。将 N 个元素添加到列表中需要 O(N) 的时间。连续执行这些操作需要大约 O(N*log(N)) 的时间。
• 对列表进行二分需要 O(log(n)) 的时间。向列表中插入一个元素需要 O(N) 的时间。在 for 循环内连续执行 N 次这两个操作需要 O(N * (N + log(n))) == O(N^2) 的时间。
• O(N^2) 比 O(N*log(N)) 更慢，因此你的 p1 比你的 p2 快。

- Kevin

Answer 2

在 bisect 的情况下，您需要进行N次操作（每个操作平均成本为查找插入点的log(N)加上额外的O(N)步骤来插入项）。 总体复杂度为：O(N^2)。

而使用sort ，您只需要一个Nlog(N) 的排序步骤（加上一开始构建列表所需的N个O(1) 步骤）。 总体复杂度为：O(Nlog(N))

另请注意，sort 实现了非常优化的C代码（因为bisect 会更频繁地调用各种比较函数，所以它不像sort 那样被高度优化）

- mgilson

Answer 3

为了理解时间差异，让我们看看你实际上在做什么。

在第一个例子中，你正在拿一个空列表，并将项目添加到其中，在最后进行排序。

向列表添加元素非常便宜，它的平均时间复杂度为O(1)。它不能真正是常量时间，因为底层数据结构是一个简单的数组，随着列表的增长而最终需要扩展。这是每隔一段时间完成的，这会导致分配新数组并复制数据。那就有点贵了。但总的来说，我们仍然说这是O(1)。

接下来是排序。Python使用Timsort非常高效。这在平均和最坏情况下都是O(n log n)。所以总体而言，我们得到了遵循O(n log n)的常数时间，因此排序是唯一重要的事情。总的来说，这非常简单且非常快速。

第二个例子使用 bisect.insort。这利用了列表和二分搜索，以确保列表始终有序。

实质上，在每次插入时，它将使用二分搜索来查找正确的位置来插入新值，然后正确地移动所有项以在该索引处为新值腾出空间。二分搜索很便宜，平均为O(log n)，因此这不是问题。仅移位也不那么困难。在最坏的情况下，我们需要将所有项目向右移动一个索引，因此我们得到O(n)（这基本上是列表中的插入操作）。

因此，总体而言，我们最坏的情况下会得到线性时间。但是，我们在每个迭代中都要执行此操作。因此，在插入n个元素时，每次都需要O(n)。这导致了二次复杂度，O(n²)。这是一个问题，最终会减慢整个过程的速度。

这告诉我们什么？将插入排序应用于列表以获得排序结果并不是真正的高效方法。当我们只进行少量操作时，可以使用bisect模块来保持已排序列表的顺序，但当实际存在未排序数据时，将整个数据排序更容易。

- poke

---

公平地说，timsort 在你刚刚向已排序的列表中添加元素后也会表现出色，因为它会有一个非常长的 "gallop" 阶段。它可能仍然具有与 bisect.insort 相当的性能... - mgilson

Answer 4

数据结构中的插入和删除操作有时可能会非常昂贵，特别是如果输入数据值的分布是随机的。而排序则可能出乎意料地快。

一个关键考虑因素是，您是否可以“累加所有值”，然后对它们进行一次排序，然后“一次性”使用排序结果。如果可以的话，那么排序几乎总是非常明显地更快。

如果你记得旧的科幻电影（当时电脑被称为“巨型大脑”，每部电影总是有旋转的磁带驱动器），那就是他们据说正在处理的类型：将“排序”的更新应用于“同样排序”的主要磁带上，以产生新的“还是已排序的”主要磁带。不需要随机访问。（这是个好事，因为那时我们确实做不到。）这仍然是处理大量数据的有效方法。

- Mike Robinson