2

如果我有一个包含 300k 个元素的长未排序列表，是否会先对该列表进行排序，然后在列表上执行“for”循环以加快代码速度？无论如何，我都需要做一个“for循环”，不能使用列表理解。

sortedL=[list].sort() 

for i in sortedL:
  (if i is somenumber)
     "do some work"

我如何向 python 发出 sortedL 已排序而不是读取整个列表的信号。对列表进行排序有什么好处吗？如果有那么我该如何实施？

4

3 回答 3

8

您似乎正在考虑对列表进行排序，以便您可以快速查找somenumber.

排序是否值得取决于您是要搜索一次还是重复搜索：

  • 如果您只搜索一次，对列表进行排序不会加快速度。只需遍历列表以查找元素，就完成了。

  • 另一方面，如果您需要重复搜索值，请务必对列表进行预排序。这将使您能够用于bisect快速查找值。

第三种选择是将元素存储在dict. 这可能会提供最快的查找，但可能会比使用列表的内存效率低。

于 2012-12-18T21:20:45.493 回答
3

forpython中循环的成本不取决于输入数据是否排序。

话虽如此，如果您先排序，您可能能够提前break退出for循环或在算法级别保存其他计算。

于 2012-12-18T21:14:01.900 回答
3

如果要在 sorted 中进行搜索list，则需要一种利用排序的算法。

一种可能性是内置bisect模块。这使用起来有点麻烦，但是文档中有一个用于在其之上构建简单排序列表函数的方法。

有了这个食谱，你可以这样写：

i = index(sortedL, somenumber)

当然，如果您只是为了加快单个搜索的速度而进行排序，这有点愚蠢。排序需要 O(N log N) 时间，然后搜索需要 O(log N)，总共需要 O(N log N)；仅进行线性搜索将花费 O(N) 时间。因此，除非您通常在同一个列表上进行 log N 次搜索，否则这是不值得的。

如果您实际上不需要排序，只需要快速查找，则可以使用 aset而不是 a list。这使您可以 O(1) 查找除病理情况外的所有情况。

Also, if you want to keep a list sorted while continuing to add/remove/etc., consider using something like blist.sortedlist instead of a plain list.

于 2012-12-18T21:22:02.920 回答