使用生成器表达式而不是列表的sorted()

第一件事 sorted() 将数据转换为列表。基本上,实现的第一行(在参数验证之后)是

newlist = PySequence_List(seq);

the full source code version 2.7 和 version 3.1.2 .

:如 answer by aaronasterling ,变量 newlist 是,嗯,是

最简单的方法是使用 timeit 它告诉我传递列表比传递生成器更快:

>>> import random
>>> randomlist = range(1000)
>>> random.shuffle(randomlist)
>>> import timeit
>>> timeit.timeit("sorted(x for x in randomlist)",setup = "from __main__ import randomlist",number = 10000)
4.944492386602178
>>> timeit.timeit("sorted([x for x in randomlist])",setup = "from __main__ import randomlist",number = 10000)
4.635165083830486

>>> timeit.timeit("sorted(x for x in xrange(1000,1,-1))",number = 10000)
1.411807087213674
>>> timeit.timeit("sorted([x for x in xrange(1000,1,-1)])",number = 10000)
1.0734657617099401

我想这是因为 sorted() 将传入值转换为列表对于已是列表的内容,它可以比对于生成器更快地执行此操作。 The source code seems to confirm this

这是一个巨大的好处。因为sorted不会影响传入的序列,所以它必须对其进行复制。如果它从生成器表达式中生成列表,则只生成一个列表。如果传入列表理解,则首先生成该列表,然后 sorted 复制一份进行排序。

这反映在

newlist = PySequence_List(seq);

引用于 Sven Marnach's answer . 本质上,这将无条件地复制传递给它的任何序列。

如果不知道序列的所有元素,就无法对序列进行排序,因此任何生成器都将传递给 sorted()

Python使用Timsort。Timsort需要知道前面的元素总数,才能计算minrun参数。因此,正如Sven所报告的,当给定一个生成器时,sorted所做的第一件事就是将它变成一个列表。

也就是说,编写Timsort的增量版本是可能的,它消耗生成器中的值的速度会更慢-您只需在开始之前修复minrun,并接受在结束时进行一些不平衡合并的痛苦。Timsort分两个阶段工作。第一个阶段涉及整个数组的传递,标识运行并执行插入排序,以便在数据无序的地方运行。运行查找和插入排序本质上都是增量的。第二个阶段涉及排序运行的合并;这与现在完全一样。

不过,我觉得这没什么意义。也许这会使内存管理变得更容易,因为不必从生成器读取到不断增长的数组中(正如我毫无根据地假设当前实现所做的那样),您可以将每次运行读取到一个小缓冲区中,然后在最后只分配一次最终大小的缓冲区。然而,这将涉及在内存中同时有2N个数组槽,而一个增长的数组可以用1.5N来完成,如果它在增长时加倍。所以,可能不是个好主意。

我最初还认为 理解比列表快

for ? 为此,我将说这取决于:列表理解更像是一种语法糖,但当涉及到简单循环时,它非常方便。

知道。寄东西有什么好处吗 要排序的生成器表达式() 而不是单子?

列表理解和生成器表达式的主要区别在于,生成器表达式避免了一次生成整个列表的开销。相反,它们返回一个生成器对象,该对象可以逐个迭代,因此生成器表达式更有可能用于节省内存使用。

但是你必须理解Python中的一件事:仅仅通过观察,很难判断一种方法是否比另一种方法更快(乐观),如果你想这么做,你应该使用 timeit

阅读 this 有关一些优化技术的更多信息。

直接地 ,它 更快;大部分开销可能是代码创建自己的列表或生成器:

>>> timeit.timeit("sorted(xrange(1000, 1, -1))", number=10000)
0.34192609786987305
>>> timeit.timeit("sorted(range(1000, 1, -1))", number=10000)
0.4096639156341553
>>> timeit.timeit("sorted([el for el in xrange(1000, 1, -1)])", number=10000)
0.6886589527130127
>>> timeit.timeit("sorted(el for el in xrange(1000, 1, -1))", number=10000)
0.9492318630218506

如果性能很重要,为什么不按生成器生成的数据进行处理,并对迭代结果应用排序呢?当然,这只能在迭代之间没有因果条件的情况下使用(即排序迭代的数据不需要进行排序迭代的计算)。