從python中的另一個排序列表中移除排序列表的快速和pythonic /乾淨的方式是什麼？

Question

我正在創建一個快速方法來生成範圍內的素數列表（0，limit + 1）。在函數中，我最終從名爲primes的列表中刪除名爲可移動的列表中的所有整數。我正在尋找一種快速和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代碼，因爲set s的解決方案的操作是用C語言實現的，因此它們速度很快（即具有一個很小的常量），所以對於n的小實際值確實可能會慢一些。

如果您有多個工作解決方案，請在典型的輸入尺寸上運行它們並測量時間。你可能會對它們的相對速度感到驚訝，但這往往不是你所預測的。

Answer 2

這裏最重要的是消除二次行爲。你有這個原因有兩個。

首先，調用remove搜索整個列表以刪除值。這樣做需要線性時間，並且您爲removable中的每個元素執行一次，所以您的總時間爲O(NM)（其中N是primes的長度，而M的長度是removable的長度）。

其次，從列表中移除元素會迫使您將整個列表的其餘部分向上移動一個插槽。所以，每一個都需要線性時間，並且再次執行M次，所以再次是O(NM)。

---

如何避免這些？

首先，您需要利用排序，或者只是使用一些可以進行常量查找而不是線性時間的方法，如set。

對於第二個，你需要創建一個要刪除的索引列表，然後執行第二遍來將每個元素一次移動到適當數量的索引上，或者只是建立一個新列表而不是試圖變異原來的就地。

因此，這裏有各種選擇。哪一個最好？這幾乎肯定沒有關係;將您的O(NM)時間更改爲O(N+M)可能足以滿足您對結果滿意的優化。但是如果你需要擠出更多的性能，那麼你必須實現所有這些並且在真實的數據上測試它們。

我認爲這些中唯一不明顯的是如何「使用排序」。我們的想法是使用同一種交錯拉鍊迭代的，你會在合併排序使用，就像這樣：

def sorted_subtract(seq1, seq2): 
    i1, i2 = 0, 0 
    while i1 < len(seq1): 
     if seq1[i1] != seq2[i2]: 
      i2 += 1 
      if i2 == len(seq2): 
       yield from seq1[i1:] 
       return 
     else: 
      yield seq1[i1] 
      i1 += 1