4

我对它并不陌生，但我不怎么使用 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)

谁能告诉我其中之一是否明显更有效？我倾向于第二组陈述，但我真的不知道。

4

2 回答 2

7

您正在寻找的是 bisect 模块和最有可能的insort_left

所以你的表达式可以等效地写成

从

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

至

bisect.insort_left(some_list, item)
于 2013-02-13T19:21:02.587 回答
2

插入除末尾附近的任何地方都需要 O(n) 时间，因为它必须移动（复制）插入点之后的所有元素。但另一方面，所有基于比较的排序算法平均必须进行 Omega(n log n) 比较。许多排序（包括 Python 使用的 timsort）在许多输入上会做得更好，可能包括你的（“几乎排序”的情况）。他们仍然必须移动至少与立即插入正确位置一样多的元素。他们还必须做很多额外的工作（检查所有元素以确保它们的顺序正确，加上更复杂的逻辑，通常可以提高性能，但在你的情况下不是）。由于这些原因，它可能会更慢，至少对于大型列表而言。

由于是用 C 编写的（在 CPython 中；但类似的推理适用于其他 Python），它可能仍然比 Python 编写的线性扫描更快。这就留下了如何找到插入点的问题。二进制搜索可以在 O(log n) 时间内完成这部分，所以在这里非常有用（当然，插入仍然是 O(n)，但如果你想要一个排序列表，就没有办法解决这个问题）。不幸的是，二分搜索实现起来相当棘手。幸运的是，它已经在标准库中实现了：bisect.

于 2013-02-13T19:26:43.877 回答