O (1) deque de números enteros indexables en Python

Question

¿Cuáles son mis opciones allí? Necesito llamar a un montón de append s (al extremo derecho) y popleft s (desde el extremo izquierdo, naturalmente), pero también para leer desde la mitad del almacenamiento, que crecerá constantemente, por la naturaleza del algoritmo. Me gustaría tener todas estas operaciones en O(1).

Podría implementarlo en C con bastante facilidad en una matriz con dirección circular (¿cuál es la palabra?) Que crecería automáticamente cuando esté llena; pero ¿qué hay de Python? También se agradecen los punteros a otros idiomas (me doy cuenta de que la etiqueta "collections" está más orientada a Java, y agradecería la comparación, pero como objetivo secundario).

Vengo de un fondo Lisp y me sorprendió saber que en Python, la eliminación de un elemento principal de una lista es una operación O(n). Un deque podría ser una respuesta, excepto que la documentación dice que el acceso es O(n) en el medio. ¿Hay algo más, preconstruido?

Answer 1

Puede obtener una estructura de datos O (1) amortizada utilizando dos listas de Python, una sosteniendo la mitad izquierda del deque y la otra sosteniendo la mitad derecha. La mitad frontal se almacena invertida, por lo que el extremo izquierdo del deque se encuentra en la parte posterior de la lista. Algo como esto:

class mydeque(object): 

    def __init__(self): 
    self.left = [] 
    self.right = [] 

    def pushleft(self, v): 
    self.left.append(v) 

    def pushright(self, v): 
    self.right.append(v) 

    def popleft(self): 
    if not self.left: 
     self.__fill_left() 
    return self.left.pop() 

    def popright(self): 
    if not self.right: 
     self.__fill_right() 
    return self.right.pop() 

    def __len__(self): 
    return len(self.left) + len(self.right) 

    def __getitem__(self, i): 
    if i >= len(self.left): 
     return self.right[i-len(self.left)] 
    else: 
     return self.left[-(i+1)] 

    def __fill_right(self): 
    x = len(self.left)//2 
    self.right.extend(self.left[0:x]) 
    self.right.reverse() 
    del self.left[0:x] 

    def __fill_left(self): 
    x = len(self.right)//2 
    self.left.extend(self.right[0:x]) 
    self.left.reverse() 
    del self.right[0:x] 

no estoy 100% seguro de si la interacción entre el código y el rendimiento amortizado de las listas de pitón en realidad resulta en O (1) para cada operación, pero mi instinto dice así.

Answer 2

Acceder a la mitad de una lista de lisp también es O (n).

Python list s son listas de matrices, razón por la cual es costoso hacer estallar la cabeza (abrir la cola es un tiempo constante).

Lo que está buscando es una matriz con eliminaciones de tiempo constante (amortizadas) en la cabecera; eso significa básicamente que tendrá que construir una estructura de datos además de list que usa la eliminación diferida, y puede reciclar las ranuras borradas de forma lenta cuando la cola está vacía.

Como alternativa, utilice una tabla hash y un par de enteros para realizar un seguimiento del rango contiguo actual de claves.

Answer 3

Python's Queue Module puede ayudarle, aunque no estoy seguro de si el acceso es O(1).