python - ordered - ¿Cómo cortar un deque?

python 3.6 deque

Question

Esta pregunta ya tiene una respuesta aquí:

• Usa la notación de división con colecciones. 4 respuestas

He cambiado algún código que utiliza una lista para usar un deque. Ya no puedo cortarlo, ya que me sale el error:

TypeError: el índice de secuencia debe ser entero, no ''slice''

Aquí hay un REPL que muestra el problema.

>>> 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''

Entonces, ¿hay alguna solución para admitir la división en deques en Python?

Answer 1

Probar itertools.islice() .

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

La indexación en un deque requiere seguir una lista vinculada desde el principio cada vez, por lo que el enfoque islice() , omitiendo elementos para llegar al inicio del segmento, proporcionará el mejor rendimiento posible (mejor que codificarlo como una operación de índice para cada uno). elemento).

Podrías escribir fácilmente una subclase deque que haga esto automáticamente por ti.

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)

Tenga en cuenta que no puede utilizar índices negativos o valores de paso con islice . Es posible codificar alrededor de esto, y podría valer la pena hacerlo si toma el enfoque de subclase. Para un inicio o una parada negativos, simplemente puede agregar la longitud del deque; para el paso negativo, deberás lanzar un reversed() en alguna parte. Dejaré eso como un ejercicio. :-)

El rendimiento de la recuperación de elementos individuales del deque se reducirá ligeramente por la prueba if de la división. Si se trata de un problema, puede usar un patrón de EAFP para mejorar esto, a costa de hacer que la ruta de la división tenga un poco menos rendimiento debido a la necesidad de procesar la excepción:

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

Por supuesto, todavía hay una llamada a la función adicional, en comparación con un deque regular, así que si realmente te importa el rendimiento, realmente quieres agregar un método separado de slice() o similar.

Answer 2

Si el rendimiento es una preocupación, considere un método de acceso / comprensión directa como se sugiere en esta respuesta . Es mucho más rápido que islice en grandes colecciones:

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

Según el comentario de @RaymondHettinger a continuación, el método de comprensión solo es mejor cuando los cortes son cortos. En rebanadas más largas, islice gana convincentemente. Por ejemplo, aquí están los tiempos para cortar un corte de 10,000 artículos del desplazamiento 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

La comprensión hace primero algunos cortes muy rápidos, pero el rendimiento cae dramáticamente a medida que crece la longitud. islice es más lento en rebanadas más pequeñas, pero su velocidad promedio es mucho mejor.

Así es como lo probé:

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)