列表、集合还是生成器？

理论上，如果检查将执行一次，那么最好使用生成器，因为 在这种情况下，将仅通过序列到达所需元素（或到序列末尾，如果该元素不在其中）。要创建set或list解释，有必要绕过整个元素集一次，然后搜索它。

如果检查将执行多次（例如，在循环中），那么最好提前创建一个现成的set，然后检查 this 中已经存在的元素set。

以供参考：

• 列表或生成器搜索是线性搜索（即，只是元素的顺序迭代，直到找到所需的元素），搜索时间与序列的长度成正比 ( O(n))
• Python 中的集合被实现为哈希表，查找时间（平均）不依赖于元素的数量，它总是大致相同（О(1)）。但是由于 哈希表的内部结构比列表更复杂，创建集合需要更多时间。

这是一个理论，在实践中，在没有先保存到变量的情况下进行搜索时，我们得到以下结果：

我们看到列表搜索结果比生成器搜索稍快。很可能是因为在生成器中获取下一个元素比在列表中花费更多的时间。

为了评估预处理搜索的实际性能，我们编写了以下程序：

n = 10000000
a = (n-1)**2  # худший случай для линейного поиска

s_list = [i*i for i in range(n)]
s_set = {i*i for i in range(n)}
s_gen = (i*i for i in range(n))

def in_list():
    return a in s_list

def in_set():
    return a in s_set

def in_gen():
    return a in s_gen

print(in_list())
print(in_set())
print(in_gen())

使用探查器运行：

python3 -m cProfile -s time test.py

结果：

True
True
True
         10000011 function calls in 3.927 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    1.976    1.976    1.976    1.976 test.py:5(<setcomp>)
 10000000    0.768    0.000    0.768    0.000 test.py:6(<genexpr>)
        1    0.625    0.625    1.393    1.393 test.py:14(in_gen)
        1    0.489    0.489    0.489    0.489 test.py:4(<listcomp>)
        1    0.069    0.069    0.069    0.069 test.py:8(in_list)
        3    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    3.927    3.927 test.py:1(<module>)
        1    0.000    0.000    3.927    3.927 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 test.py:11(in_set)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

我们看到，就创建时间而言，集合 ( <setcomp>) 的创建速度最慢，然后是生成器 ( <genexpr>)，然后是列表 ( <listcomp>)。

按搜索时间：最慢 - 按生成器搜索 ( in_gen)，快一点 - 按列表 ( in_list)，最快 - 在集合中搜索 ( in_set)。

口译员：

Python 3.6.8 (default, Aug 20 2019, 17:12:48) 
[GCC 8.3.0] on linux

结果：

• 在不先保存到变量的情况下进行搜索时，最好使用列表。但是，如果有内存限制，最好使用生成器。
• 使用 prestore 搜索时，最好使用 set