为什么从过滤器创建集合比创建列表或元组快得多？

Question

我在一个可迭代对象上使用了 filter，想把结果存储在一个序列中（我需要一个序列，这样才能用 random.choice）。我发现从 filter 对象创建一个 set 要比创建一个 list 或 tuple 快很多。为什么会这样呢？我最开始以为 filter 类型是 set 的一种子类型，这样就能解释这个现象，但其实 filter 函数和生成器表达式是一样的，所以它内部不可能真的是一个 set。

我进行了以下测试来检查速度：

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 更好：

set 1.9240000247955322
list 8.82200002670288
tuple 7.031999826431274

那么，为什么从 filter 创建一个 set 会这么快呢？难道它不应该和从一个序列创建 set 一样慢吗？因为每个元素都需要进行哈希处理？还是说它在内部的 filter 表示上得到了某种提升？

为了比较，当我在 range 表达式上运行测试时，set 的速度大约是 list 和 tuple 的两倍（这两者的速度几乎是一样的）。

编辑：

Sven 的回答完全正确，但为了完整性，我进行了一个更新的测试，实际运行在一个 filter 上：

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

Answer 1

当时间测量的结果看起来不合理时，往往是测量的工具出了问题；-)

可以试试使用 timeit模块，这个工具可以帮助你避免常见的时间测量错误。特别是，你应该为每次测试准备一个新的 setup，并且只测量循环内部的代码，而不是包括测试代码在内的全部内容。

在这种情况下，这样做至少会让时间测量变得可比（所有的测量都会使用一个新的迭代器，这个迭代器是Python 3的*filter返回的），而且会显示出非常快的时间（因为在循环中只测量了 method(iterator) 这段代码）。

顺便说一下，pypy 的时间测量会更困难，因为过于简单的循环会被完全优化掉。

[对问题的回答经过编辑] 你新的时间测量结果是可以比较的（这是个不错的进步），但结果仍然显示出设置时间和循环时间的结合，让你很难看出可能重要的差异。你应该预期列表和元组会比集合快，因为集合需要做更多的工作（对每个输入进行哈希处理，而不是简单地存储它们）。

Answer 2

filter() 在 Python 3 中会返回一个迭代器，而这个迭代器在第一次运行内部的 for 循环时就会被消耗掉。之后，你只是在测量构造器的速度——这就是为什么你需要重复多次，以确保它至少消耗一点时间。

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