O (1) deque indicizzabile di interi in Python

Question

quali sono le mie opzioni lì? Ho bisogno di chiamare un sacco di append s (all'estremità destra) e popleft s (dall'estremità sinistra, naturalmente), ma anche di leggere dal centro dello storage, che crescerà costantemente, secondo la natura dell'algoritmo. Mi piacerebbe avere tutte queste operazioni in O(1).

Potrei implementarlo in C abbastanza facilmente su array con indirizzo circolare (come si dice?) Che crescerebbe automaticamente quando è pieno; ma per quanto riguarda Python? Anche i puntatori ad altre lingue sono apprezzati (mi rendo conto che il tag "collections" è più orientato a Java ecc. E apprezzerebbe il confronto, ma come obiettivo secondario).

Provengo da uno sfondo Lisp e sono rimasto stupito nell'apprendere che in Python la rimozione di un elemento head da un elenco è un'operazione O(n). A deque potrebbe essere una risposta, tranne la documentazione dice che l'accesso è O(n) nel mezzo. C'è qualcos'altro, pre-costruito?

Answer 1

È possibile ottenere una struttura di dati O (1) ammortizzata utilizzando due elenchi python, uno contenente la metà sinistra del deque e l'altro con la metà destra. La metà anteriore è memorizzata in senso inverso in modo che l'estremità sinistra del deque si trovi sul retro della lista. Qualcosa di simile a questo:

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] 

non sono sicuro al 100% se l'interazione tra questo codice e le prestazioni ammortizzato delle liste di Python in realtà risultato in O (1) per ogni operazione, ma il mio istinto dice così.

Answer 2

Anche l'accesso al centro di una lista Lisp è O (n).

Python list s sono elenchi di array, motivo per cui il popping della testina è costoso (facendo scattare la coda è un tempo costante).

Quello che stai cercando è un array con cancellazioni a tempo costante (ammortizzate) alla testa; ciò significa fondamentalmente che dovrai costruire una struttura dati su list che utilizza l'eliminazione lenta e che è in grado di riciclare gli slot cancellati pigramente quando la coda è vuota.

In alternativa, utilizzare una tabella hash e un paio di numeri interi per tenere traccia dell'attuale gamma di chiavi contigue.

Answer 3

Python's Queue Module può aiutarti, anche se non sono sicuro che l'accesso sia O(1).