python - 从 python 中的另一个排序列表中删除排序列表的快速和 pythonic/clean 方法是什么？

Question

我正在创建一种快速生成范围 (0, limit+1) 内素数列表的方法。在函数中，我最终从名为 primes 的列表中删除了名为 removable 的列表中的所有整数。我正在寻找一种快速且 pythonic 的方式来删除整数，因为我知道这两个列表总是排序的。

我可能是错的，但我相信 list.remove(n) 遍历列表，将每个元素与 n 进行比较。这意味着以下代码在 O(n^2) 时间内运行。

# removable and primes are both sorted lists of integers
for composite in removable:
    primes.remove(composite)

基于我的假设(这可能是错误的，请确认这是否正确)以及两个列表总是排序的事实，我认为下面的代码运行得更快，因为它只在列表上循环一次O(n) 时间。但是，它根本不是 pythonic 或干净的。

i = 0
j = 0
while i < len(primes) and j < len(removable):
    if primes[i] == removable[j]:
        primes = primes[:i] + primes[i+1:]
        j += 1
    else:
        i += 1

是否有内置函数或更简单的方法？最快的方法是什么？

旁注:我实际上并没有为上面的函数或代码计时。此外，可移动列表是否在此过程中被更改/销毁也没关系。

对于所有感兴趣的人，完整功能如下:

import math

# returns a list of primes in range(0, limit+1)
def fastPrimeList(limit):
    if limit < 2:
        return list()
    sqrtLimit = int(math.ceil(math.sqrt(limit)))
    primes = [2] + range(3, limit+1, 2)
    index = 1
    while primes[index] <= sqrtLimit:
        removable = list()
        index2 = index
        while primes[index] * primes[index2] <= limit:
            composite = primes[index] * primes[index2]
            removable.append(composite)
            index2 += 1
        for composite in removable:
            primes.remove(composite)
        index += 1
    return primes

Answer 1

这是非常快速和干净的，它确实 O(n) 设置成员检查，并且在摊销时间内它在 O(n) 中运行(第一行是 O(n) 摊销，第二行是 O(n * 1) 摊销，因为成员资格检查是 O(1) 摊销:

removable_set = set(removable)
primes = [p for p in primes if p not in removable_set]

这是对您的第二个解决方案的修改。它执行 O(n) 基本操作(最坏情况):

tmp = []
i = j = 0
while i < len(primes) and j < len(removable):
    if primes[i] < removable[j]:
        tmp.append(primes[i])
        i += 1
    elif primes[i] == removable[j]:
        i += 1
    else:
        j += 1
primes[:i] = tmp
del tmp

请注意常量也很重要。 Python 解释器执行 Python 代码的速度非常慢(即常量很大)。第二个解决方案有很多 Python 代码，对于 n 的小实际值，它确实比使用 set 的解决方案慢，因为 set 操作是在 C 中实现的，因此它们很快(即常数很小)。

如果您有多个可行的解决方案，请在典型的输入大小上运行它们，并测量时间。您可能会对它们的相对速度感到惊讶，这通常不是您所预料的。