5

我正在filter一个可交互的设备上运行,并希望将结果存储在一个序列中(我需要一个序列以便我可以使用random.choice它)。我注意到从过滤器对象创建集合比创建列表元组快得多。这是为什么?我首先认为过滤器类型是集合的子类型,这可以解释这一点,但该函数实际上与生成器表达式相同,因此它在内部不能真正成为集合。filter

我运行了以下测试来检查速度:

import time

def test ( n, seq ):
    for method in ( set, list, tuple ):
        t = time.time()
        for i in range( n ):
            method( seq )
        print( method.__name__, ( time.time() - t ) )

someFilter = filter( lambda x: x % 3 == 0, range( 1000 ) )
test( 10000000, someFilter )

结果清楚地说明了使用集合:

set 1.9240000247955322
list 8.82200002670288
tuple 7.031999826431274

那么为什么从过滤器创建一个集合的速度如此之快呢?它通常不应该像从序列中创建一个集合一样长,其中每个元素都必须被散列吗?或者它是否以某种方式从内部过滤器表示中得到了提升?

相比之下,在对range表达式运行测试时,所需时间大约是和set的两倍(两者的速度几乎相同)。listtuple

编辑:

Sven 的回答是完全正确的,但为了完整性,更新的测试将在实际过滤器上运行:

import time

def testFilter ( n, test, rangeSize ):
    for method in ( set, list, tuple ):
        t = time.time()
        for i in range( n ):
            method( filter( test, range( rangeSize ) ) )
        print( method.__name__, ( time.time() - t ) )

testFilter( 100000, lambda x: x % 3 == 0, 1000 )

结果实际上显示了什么更有意义,list并且tuple两者都是最快的,尽管 set 并不是真的很慢,所以使用什么不会有任何区别:

set 27.868000030517578
list 27.131999969482422
tuple 27.138000011444092
4

2 回答 2

11

filter()在 Python 3 中返回一个迭代器,这个迭代器将在内部 for 循环的第一次运行时使用。在那之后,你只是在测量构造器的速度——这就是为什么你必须经常重复它以使它至少消耗一点时间。

所以看起来构造函数set()是处理空迭代器最快的。

于 2011-11-10T23:20:08.793 回答
4

当时序显示不合逻辑的结果时,通常是时序套件本身有问题;-)

尝试使用timeit 模块,它可以帮助您避免常见的计时错误。特别是,您希望为每个测试运行一个全新的设置,并且只对循环主体而不是主体加上测试代码进行计时。

在这种情况下,它至少可以使时间具有可比性(它们都将使用 Python 3 的 *filter 版本返回的新迭代器)并且它会显示出令人难以置信的快速时间(因为只有method(iterator)代码会被计时在一个循环中)。

FWIW,pypy将更加难以计时,因为过于简单的循环会被完全优化掉。

[对已编辑问题的回答]您的新时间具有可比性(一个很好的改进),但结果仍然显示设置时间和循环时间的组合,因此很难看到可能显着的差异。您的期望应该是列表和元组击败集合,因为集合必须做更多的工作(散列每个输入而不是简单地存储它们)。

于 2011-11-10T23:29:32.503 回答