如何切片一个双端队列？

Question

我已经将一些使用列表的代码更改为使用双向队列(deque)。但是，当我尝试进行切片操作时，出现以下错误：

TypeError：序列索引必须为整数，而不是“slice”

这里有一个REPL演示了这个问题。

>>> import collections
>>> d = collections.deque()
>>> for i in range(3):
...     d.append(i)
...
>>> d
deque([0, 1, 2])
>>> d[2:]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'

那么，在Python中是否有支持切片deque的解决方法？

- Drew Noakes

---

@HunterMcMillen，感谢您的评论。我正在使用deque来提高性能（实际上是作为循环缓冲区），因此每个周期将数据复制到列表中并不理想。 - Drew Noakes

使用切片符号与collections.deque - georg

@thg435，感谢您提供的交叉引用。我在谷歌上搜索了错误字符串，但在SO上没有找到任何相关内容，因此发布了这个新问题。那里也有一些很好的见解。 - Drew Noakes

Answer 1

尝试使用 itertools.islice()。

 deque_slice = collections.deque(itertools.islice(my_deque, 10, 20))

访问 deque 中的元素需要每次从开头开始遍历链表，因此使用 islice() 方法跳过未被切片的元素并定位到切片的起始位置能够获得最佳性能表现（比对每个元素进行索引操作更快）。

你可以轻松编写一个 deque 子类来自动执行该操作。

class sliceable_deque(collections.deque):
    def __getitem__(self, index):
        if isinstance(index, slice):
            return type(self)(itertools.islice(self, index.start,
                                               index.stop, index.step))
        return collections.deque.__getitem__(self, index)

请注意，您不能在 islice 中使用负索引或步长值。如果采用子类方法，可能可以绕过这个问题，并且这样做可能是值得的。对于负数的起始或停止位置，您只需要添加 deque 的长度即可；对于负数的步长值，需要在某个地方加入 reversed()。我会把这留给你作为练习。:-)

从 deque 检索单个元素的性能将因对切片进行 if 测试而稍微降低。如果这是一个问题，可以使用 EAFP 模式来缓解这个问题--代价是使切片路径略微不太高效，因为需要处理异常:

class sliceable_deque(collections.deque):
    def __getitem__(self, index):
        try:
            return collections.deque.__getitem__(self, index)
        except TypeError:
            return type(self)(itertools.islice(self, index.start,
                                               index.stop, index.step))

当然，与普通的deque相比，这里仍存在额外的函数调用，所以如果你真的关心性能，你真的应该添加一个单独的slice()方法或类似的方法。

- kindall

---

谢谢，我在一个可变长度的缓冲区上使用了负索引，但每个实例的长度都是固定的。所以，我改变了我的逻辑，并使其成为每个实例的正索引。这是一个更加明智的权衡。 - RobotHumans

我期望一个可切片的deque也能实现对切片的__setitem__和__delitem__。还有一个问题，为什么在except:分支中返回type(self)(...)（这表明您想要协作继承），但在try:块中明确引用了collections.deque而不是使用super（这表明您不想要协作继承）。我有什么遗漏吗？ - wim

Answer 2

如果性能是一个问题，考虑使用直接访问/理解方法，正如这个答案所建议的那样。它比对大型集合使用islice要快得多：

import timeit

setup = """
import collections, itertools
d = collections.deque(range(10000))
"""

print timeit.timeit('list(itertools.islice(d, 9000, 9010))', setup, number=10000)
## 0.631947040558
print timeit.timeit('[d[i] for i in range(9000, 9010)]', setup, number=10000)
## 0.0292208194733

根据@RaymondHettinger的评论，当切片较短时，推导式方法才更好。在更长的切片上，islice胜出。例如，这里是从偏移量6000切片一个包含10000个项的deque的时间：

偏移量  长度       islice        compr
 6000     10      400.496      46.611
 6000     50      424.600     183.988
 6000     90      432.277     237.894
 6000    130      441.289     352.383
 6000    170      431.299     404.596
 6000    210      456.405     546.503
 6000    250      448.895     575.995
 6000    290      485.802     778.294
 6000    330      483.704     781.703
 6000    370      490.904     948.501
 6000    410      500.011     875.807
 6000    450      508.213    1045.299
 6000    490      518.894    1010.203
 6000    530      530.887    1192.784
 6000    570      534.415    1151.013
 6000    610      530.887    1504.779
 6000    650      539.279    1486.802
 6000    690      536.084    1650.810
 6000    730      549.698    1454.687
 6000    770      564.909    1576.114
 6000    810      545.001    1588.297
 6000    850      564.504    1711.607
 6000    890      584.197    1760.793
 6000    930      564.480    1963.091
 6000    970      586.390    1955.199
 6000   1010      590.706    2117.491

推导式对前几个切片的处理速度非常快，但随着长度的增加，性能急剧下降。islice在较小的切片上速度较慢，但其平均速度要好得多。

我是这样测试的：

import timeit

size = 10000
repeats = 100

setup = """
import collections, itertools
d = collections.deque(range(%d))
""" % size

print '%5s\t%5s\t%10s\t%10s' % ('offset', 'length', 'islice', 'compr')

for offset in range(0, size - 2000, 2000):
    for length in range(10, 2000, 40):
        t1 = timeit.timeit('list(itertools.islice(d, %d, %d))' % (offset, offset + length), setup, number=repeats)
        t2 = timeit.timeit('[d[i] for i in range(%d, %d)]' % (offset, offset + length), setup, number=repeats)
        print '%5d\t%5d\t%10.3f\t%10.3f' % (offset, length, t1 * 100000, t2  * 100000)

- georg

---

当然，这也可以包装在一个重载的__getitem__方法中。 - aaronasterling

这是一个非常令人惊讶的结果。 - kindall

这个答案非常误导性，从时间上得出了错误的结论。使用d[i]进行索引通常很快，因为查找会以62个元素为步长跨越deque，并且当“i> len(d) // 2”时，它足够聪明地从右侧遍历。但是，当您需要一个更长的切片时，逐个索引就不是一个好主意了。例如，在30000个元素的deque中尝试对切片“9000：10000”进行计时，将得到完全不同的结果。 - Raymond Hettinger

你好，@RaymondHettinger，感谢您的评论！我编辑了帖子以反映您的观点。 - georg

没有意识到 deque 使用了一种跨步技术，这很不错。 - kindall