1

有没有办法从一长串数字的开头删除元素？现在我正在做 del arr[i:i+x] 但它很慢，因为它必须将所有内容移到左侧，这对于大型列表来说很耗时。

我查看了双端队列，但不确定这些是否适用于此。可以使用一些方向！

4

5 回答 5

5

是deque的，这里确实适用，你应该使用它们，如果它们非常靠近前面，它将非常快，但如果起始索引位于中间，则速度会慢一些。

索引访问在两端都是 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。

于 2013-04-24T03:01:30.757 回答
1

是的，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])
于 2013-04-24T03:05:09.683 回答
0

如果您连续进行多次删除，使用带有过滤器的生成器创建新列表可能会更有效：

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)。

于 2013-04-24T03:18:00.807 回答
0

我想你可能想要一棵树或跳过列表。

不久前我对 Python 树的实现进行了研究： http ://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

您最好在网站的算法部分询问这个问题。

于 2013-04-24T04:00:19.417 回答
0

列表未针对在前面追加或弹出进行优化。不过，双端队列是。

另请注意，deque.remove(item)CPython实现中的将从前面搜索。如果您需要经常移动/删除队列项目，您可能会受益于考虑是否大多数要删除的项目将接近尾声并在这种情况下使用翻转队列，即appendleftandpop而不是appendand popleft。

于 2021-05-05T10:27:41.477 回答