python - 列表理解与过滤与删除

Question

后两种解决方案比前一种解决方案好在哪里？

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 次。

我不明白这个。我不明白它怎么能节省时间或内存。

这是书中解释这一点的段落:

To remove or insert a single item from/into the list, Python needs to copy the entire list, which is especially heavy with larger lists. When executing this only once, it is of course not all that bad. But when executing a large number of deletions, a filter or list comprehension is a much faster solution because, if properly structured, it needs to copy the list only once. .... then the examples ... The latter two are much faster for large lists of items. This is because the operations are much faster. To compare using n=len(items) and m=len(primes), the first takes O(m*n)=5*10=50 operations, whereas the latter two take O(n*1)=10*1=10 operations.

编辑:书没有错。 primes = set((1, 2, 3, 5, 7)) 是正确的声明而不是 primes = (1, 2, 3, 5, 7)

Answer 1

如果书中的代码与您发布的代码完全相同，那么这本书完全错了。

第一个示例的时间复杂度为 O(n*m)，但其他两个也是如此。

如果 primes 是一个 set(或 dict)，那么它将为真——使用 in 进行存在性查找hashmap 中的 code> 运算符的时间复杂度为 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 快 3 个数量级/tuple, ~45us.