4

在以下简单示例中，有两个函数对随机数列表进行排序。第一个方法传递sorted一个生成器表达式，第二个方法首先创建一个列表：

import random
l = [int(1000*random.random()) for i in xrange(10*6)]

def sort_with_generator():
    return sorted(a for a in l)

def sort_with_list():
    return sorted([a for a in l])

使用line profiler进行基准测试表明，第二个选项 ( sort_with_list) 的速度大约是生成器表达式的两倍。

谁能解释发生了什么，为什么第一种方法比第二种方法慢得多？

4

3 回答 3

6

您的第一个示例是迭代列表的生成器表达式。您的第二个示例是迭代列表的列表表达式。事实上，第二个例子稍微快一些。

>>> import timeit
>>> timeit("sorted(a for a in l)", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.963912010192871
>>> timeit("sorted([a for a in l])", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.021576881408691

毫无疑问，这样做的原因是创建列表是一次性完成的，而迭代生成器需要函数调用。

生成器不会加速这样的小列表（列表中有 60 个元素，这非常小）。主要是在创建长列表时节省内存。

于 2013-09-06T02:15:17.360 回答
2

如果您查看的源代码，sorted您传入的任何序列都会首先被复制到一个新列表中。

newlist = PySequence_List(seq);

generator-->list似乎比list-->慢list。

>>> timeit.timeit('x = list(l)', setup = 'l = xrange(1000)')
16.656711101531982
>>> timeit.timeit('x = list(l)', setup = 'l = range(1000)')
4.525658845901489

至于为什么必须制作副本，请考虑排序的工作原理。排序不是线性算法。我们多次遍历数据，有时会双向遍历数据。生成器旨在生成一个序列，我们通过该序列迭代一次且仅一次，从开始到之后的某个地方。列表允许随机访问。

另一方面，从生成器创建列表意味着内存中只有一个列表，而制作列表的副本意味着内存中有两个列表。很好的老式时空权衡。

Python 使用Timsort，这是合并排序和插入排序的混合体。

于 2013-09-06T02:57:21.940 回答
0

列表表达式首先将数据加载到内存中。然后对结果列表进行任何操作。让分配时间是T2（对于第二种情况）。生成器表达式不会立即分配时间，但会更改 time 的迭代器值t1[i]。总和t1[i]将是T1。T1≈ T2.

但是当您调用时sorted()，在第一种情况下，与 sort( )T1相比，每对的分配内存时间都加上了 time 。tx1[i]结果，T1加上所有的总和tx1[i]。

因此，T2<T1 + sum(tx1[i])

于 2013-09-06T02:20:54.367 回答