Python：有效地移除列表前面的元素？

Question

有沒有辦法從一長串數字的開始處移除元素？現在我正在做del arr [i：i + x]，但它很慢，因爲它必須將所有點都移到左邊，這對於大型列表來說是非常耗時的。

我看着deques，但不知道這些是否適用於此。可以使用一些方向！

Answer 1

是deque s在這裏適用，您應該使用它們，如果它們非常靠近前方，它將會非常快，但是如果起始索引位於中間，則速度會更慢。

索引訪問兩端都是O（1），但是在中間減慢到O（n）。

>>> from collections import deque 
>>> def delete_slice(d, start, stop): 
     d.rotate(-start) 
     for i in range(stop-start): # use xrange on Python 2 
      d.popleft() 
     d.rotate(start) 


>>> d = deque(range(15)) 
>>> delete_slice(d, 5, 10) 
>>> d 
deque([0, 1, 2, 3, 4, 10, 11, 12, 13, 14]) 

注：旋轉經過中間，如前所述，將是緩慢的，如果你想支持從右側快速刪除你可以擴展的代碼如下所示：

def delete_slice(d, start, stop): 
    stop = min(stop, len(d)) # don't go past the end 
    start = min(start, stop) # don't go past stop 
    if start < len(d) // 2: 
     d.rotate(-start) 
     for i in range(stop-start): # use xrange on Python 2 
      d.popleft() 
     d.rotate(start) 
    else: 
     n = len(d) - stop 
     d.rotate(n) 
     for i in range(stop - start): 
      d.pop() 
     d.rotate(-n) 

當然，還有一些其他錯誤需要檢查，但爲了簡單起見，我會將其忽略。不幸的是，這些方法不是由deque本身提供的，所以您必須像這樣實施它們。

要實現雙端隊列切片，使用應用rotate()類似的方法，使目標元素的deque的左側。用popleft()刪除舊條目，用extend()添加新條目，然後反轉。通過這種方法的細微變化，很容易實現Forth樣式的堆棧操作，如dup，drop，swap，over，pick，rot和roll。

Answer 2

是的，deque適用於此處。準備這顯示了一個例子，如何使用它：

import collections 

"create deque from list" 
d=collections.deque([1,2,3,4,5,6]) 
"remove first element" 
d.popleft() 

print d 

輸出：

deque([2,3,4,5,6]) 

Answer 3

，如果你想保持數量爲了您沒有指定。最快的選擇是用列表末尾的數字替換列表開頭的數字。

Answer 4

如果你連續做幾缺失，它可能是更有效的創建使用生成帶有過濾器的新名單：

arr = [e for e in arr if not rejected(e)] 

如果需要使用索引工作，你可以使用列舉：

arr = [e for i, e in enumerate(arr) if not rejected(i)] 

這兩種操作是O（N）（O（2 * N）的空間），而在一個行執行若干缺失是O（n * m個）（但爲O（n）的空間） 。

deque有這個特點，你想這可能不是爲：

索引訪問是O兩端（1），但在中間放緩至O（N）。

Answer 5

我想你可能想要一棵樹或跳過列表。

我做的Python樹實現的研究而回： http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

你可能會更好，詢問有關此內容的網站的算法部分。