Как нарезать деку?

Я изменил код, который использовал список для использования 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'

Итак, есть ли обходной путь для поддержки разреза на deques в Python?

Ответ 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() или тому подобное.

Ответ 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 убедительно выигрывает. Например, здесь приведены тайминги для нарезки 10 000 элементов deque из смещения 6000:

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)