Python sorted()内置函数与list insert()方法的效率对比

Question

我对这个不算陌生，但我不太常用Python，了解的知识比较广泛，但不够深入。也许这里有更懂的人能帮我解答我的问题。我现在遇到的情况是，我需要往一个列表里添加项目，并且在添加时保持这个列表是有序的。一个快速的方法是：

list.append(item)                  // O(1)
list.sort()                        // ??

我想如果这是唯一添加项目到列表的方式，我希望每次添加时排序会比较高效，因为每次添加后列表都会保持有序。不过，还有另外一种方法也可以这样做：

inserted = False
for i in range(len(list)):         // O(N)
    if (item < list[i]): 
        list.insert(i, item)       // ??
        inserted = True
        break
if not inserted: list.append(item)

有没有人能告诉我，这两种方法中哪一种明显更高效呢？我倾向于第二种写法，但其实我也不太确定。

Answer 1

在列表中插入元素时，如果不是在最后面插入，通常需要O(n)的时间。这是因为插入点后面的所有元素都得移动（复制）到新的位置。不过，所有基于比较的排序算法平均来说，至少需要进行Omega(n log n)次比较。很多排序算法（比如Python使用的timsort）在处理某些输入时表现得更好，特别是像“几乎已经排序好的”这种情况。不过，它们仍然需要移动至少和直接插入到正确位置一样多的元素。而且，它们还需要做很多额外的工作，比如检查所有元素以确保它们的顺序正确，还有一些更复杂的逻辑来提高性能，但在你的情况下可能并没有帮助。因此，对于大列表来说，这种方法可能会更慢。

由于Python的实现是用C语言写的（在CPython中；其他Python实现也类似），所以在某些情况下，它可能比你用Python写的线性扫描要快。那么，问题就来了：如何找到插入点呢？二分查找可以在O(log n)的时间内完成这个任务，所以在这里非常有用（当然，插入仍然是O(n)，但如果你想要一个有序的列表，这是无法避免的）。不幸的是，二分查找的实现比较复杂。不过幸运的是，它已经在标准库中实现了：bisect。

Answer 2

你要找的是 bisect 模块，可能还需要用到 insort_left 这个功能。

所以你的表达式可以这样写：

从

some_list.append(item)                  // O(1)
some_list.sort()                        // ??

到

bisect.insort_left(some_list, item)