31

我已经将一些使用列表的代码更改为使用双端队列。我不能再切入它，因为我得到了错误：

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

这是一个显示问题的 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 中切片成双端队列？

4

2 回答 2

37

试试itertools.islice()。

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

索引到 adeque需要每次从头开始跟随一个链表，因此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()的方法等。

于 2012-04-04T00:04:46.637 回答
9

如果性能是一个问题，请考虑此答案中建议的直接访问/理解方法。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 个项目的双端队列的时间：

偏移长度 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)
于 2012-04-04T00:27:07.920 回答