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

Question

我正在创建一个生成范围(0,限制+ 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的小实际值,它确实比用sets 的解决方案慢,因为set操作是用C实现的,因此它们很快(即具有小的常量).

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