使用生成器表达式而不是列表排序()

Question

看到这里的讨论后:Python - 生成我很好奇的时差.我最初也认为生成器比列表更快,但是当谈到sorted()我不知道.将生成器表达式发送到sorted()而不是列表有什么好处？在排序之前,生成器表达式是否最终被放入sorted()中的列表？

编辑:让我感到悲伤的是只能接受一个答案,因为我觉得很多回复都有助于澄清这个问题.再次感谢大家.

Answer 1

首先要做的sorted()是将数据转换为列表.基本上,实现的第一行(在参数验证之后)是

newlist = PySequence_List(seq);

另请参阅完整源代码版本2.7和版本3.1.2.

编辑:正如aaronasterling在答案中指出的那样,变量newlist是一个新的列表.如果参数已经是列表,则会复制该参数.因此,生成器表达式确实具有使用更少内存的优势.

Answer 2

查看哪个更快的最简单方法是使用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()将传入的值转换为列表时,它可以更快地对已经是列表而不是生成器的事物执行此操作. 源代码似乎证实了这一点(但这是通过阅读评论而不是完全理解正在发生的一切).

Answer 3

有一个巨大的好处.因为sorted不会影响传入的序列,所以它必须复制它.如果它从生成器表达式生成列表,则只生成一个列表.如果传入列表推导,那么首先构建它,然后sorted复制它以进行排序.

这反映在该行中

newlist = PySequence_List(seq);

引用斯文马纳赫的回答.从本质上讲,这将无条件地复制传递给它的任何序列.

Answer 4

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

Answer 5

Python使用Timsort.Timsort需要知道前面元素的总数,以计算minrun参数.因此,正如Sven报道的那样,给定生成器时排序的第一件事就是将其转换为列表.

也就是说,有可能编写Timsort的增量版本,它会更慢地消耗生成器中的值 - 您只需要在启动之前修复minrun,并接受最后进行一些不平衡合并的痛苦.Timsort分两个阶段进行.第一阶段涉及遍历整个数组,识别运行并执行插入排序以在数据无序的情况下进行运行.运行查找和插入排序本质上都是递增的.第二阶段涉及合并运行的合并; 那就像现在一样.

不过,我认为这不会有很多重点.也许它会使内存管理更容易,因为你不必从生成器读入一个不断增长的数组(因为我毫无根据地假设当前的实现),你可以将每次运行读入一个小缓冲区,然后只分配一个最终 - 大小缓冲一次,最后.然而,这将涉及一次在存储器中具有2N个阵列的插槽,而如果在其增长时它增加一倍,则可以用1.5N完成增长的阵列.所以,可能不是一个好主意.