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/

你可能会更好，询问有关此内容的网站的算法部分。