如何切一个双端队列？

Question

我已经改变了一些使用列表来使用双端队列的代码.当我收到错误时,我无法再切入它:

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中切割成deques？

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.可以对此进行编码,如果采用子类方法,可能值得这样做.对于负启动或停止,您只需添加双端队列的长度; 对于消极的一步,你需要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()方法等.

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中切割10,000个项目deque的时间:

offset  length      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)