后两个如何比前一个解决方案更好？
primes = (1, 2, 3, 5, 7)
# Classic solution
items = list(range(10))
for prime in primes:
items.remove(prime)
items
# List comprehension
items = list(range(10))
[item for item in items if item not in primes]
# Filter
items = list(range(10))
list(filter(lambda item: item not in primes, items))
这三个例子是我在一本书中遇到的，它说第一个解决方案需要 O(n*m) 时间 (n=len(items), m=len(primes)) 而后两个需要 O(n* 1)时间......导致第一个解决方案的50个比较(实际上稍微好一点 - 40个比较)而后者只有10个。
我不明白。我不明白时间或内存效率如何。
书中有一段话解释了这一点:
编辑:
书没有错。
primes = set((1, 2, 3, 5, 7)) 是正确的声明，而不是 primes = (1, 2, 3, 5, 7) 最佳答案
如果书中的代码与您发布的完全相同，那么 这本书就完全错误 。
第一个示例具有时间复杂度 O(n*m) ，但其他两个也是如此。
如果 primes 是 set (或 dict )，那么它会是真的——在哈希图中使用 in 运算符进行存在查找具有时间复杂度 O(1) ，但在 list 或 tuple 中具有 O(n) !因此， O(n*m) 的总复杂度。
让我们通过一些测量来检查一下:
t = tuple(range(10000))
l = list(t)
s = set(t)
d = {i:1 for i in l}
In [16]: %%timeit
4738 in t
....:
10000 loops, best of 3: 45.5 µs per loop
In [17]: %%timeit
4738 in l
....:
10000 loops, best of 3: 45.4 µs per loop
In [18]: %%timeit
4738 in s
....:
10000000 loops, best of 3: 36.9 ns per loop
In [19]: %%timeit
4738 in d
....:
10000000 loops, best of 3: 38 ns per loop
注意
set 中的查找是 ~37ns (类似于 dict )，比 list/tuple 、 ~45us 快 3 个数量级。关于python - 列表理解 vs 过滤器 vs 删除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45042801/