¿Alguien conoce esta estructura de datos de Python?

Question

La clase Python tiene seis requisitos que se enumeran a continuación. Solo términos en negrita deben leerse como requisitos.

---

1. Cerca O (1) el rendimiento para como muchas de las cuatro operaciones siguientes.
2. Mantenimiento ordenado al insertar un objeto en el contenedor.
3. Posibilidad de vistazo al último valor (el valor más grande) contenido en el objeto.
4. Permitiendo saltos en ambos lados (obteniendo los valores más pequeños o más grandes).
5. Capacidad de obteniendo el tamaño total o la cantidad de objetos almacenados.
6. Siendo una solución preparada como el código en la biblioteca estándar de Python.

---

Lo que sigue se dejó aquí por razones históricas (ayuda a los curiosos y demuestran que la investigación se llevó a cabo).

---

Después de mirar a través de la biblioteca estándar de Python (concretamente de la sección Tipos de datos), que todavía no he encontrado una clase que cumple con los requisitos de los requisitos de una mesa de fragmentación. collections.deque está cerca de lo que se requiere, pero no es compatible con mantener ordenados los datos contenidos en él. Proporciona:

1. append eficiente y pops a cada lado de un deque con O (1) rendimiento.
2. Aparece en ambos lados para los datos contenidos en el objeto.
3. Obteniendo el tamaño total o el recuento de los objetos contenidos en.

Implementar una solución ineficiente usando listas sería trivial, pero encontrar una clase que funcione bien sería mucho más deseable. En una simulación de memoria creciente sin límite superior, dicha clase podría mantener índices de celdas vacías (eliminadas) y mantener bajos los niveles de fragmentación. El módulo bisect puede ayudar:

1. ayuda a mantener una matriz en orden ordenados mientras que la inserción nuevos objetos en serie.
2. Solución preparada para mantener listas clasificadas como objetos se agregan.
3. Permitiría ejecutar array[-1] a vistazo al último valor en la matriz.

El candidato final que no cumplió totalmente con los requisitos y parecía menos prometedor fue el módulo heapq. Mientras soportaba lo que parecían inserciones eficientes y aseguraba que array[0] era el valor más pequeño, la matriz no siempre está en un estado completamente ordenado. No se encontró nada más útil.

---

¿Alguien sabe de una estructura de clases o los datos en Python que se acerca a estos seis requisitos?

Answer 1

Muchas gracias salen a katrielalex para proporcionar la inspiración que llevó a la siguiente clase de Python:

import collections 
import bisect 

class FastTable: 

    def __init__(self): 
     self.__deque = collections.deque() 

    def __len__(self): 
     return len(self.__deque) 

    def head(self): 
     return self.__deque.popleft() 

    def tail(self): 
     return self.__deque.pop() 

    def peek(self): 
     return self.__deque[-1] 

    def insert(self, obj): 
     index = bisect.bisect_left(self.__deque, obj) 
     self.__deque.rotate(-index) 
     self.__deque.appendleft(obj) 
     self.__deque.rotate(index) 

Answer 2

Sus requisitos parecen ser:

1. O (1) emergente de cada extremo
2. eficiente len
3. fin Ordenado
4. ojeada al último valor

para el que puede usar un deque con un método personalizado insert que gira el deque, se agrega a un extremo y se deshace

>>> from collections import deque 
>>> import bisect 
>>> class FunkyDeque(deque): 
...  def _insert(self, index, value): 
...    self.rotate(-index) 
...    self.appendleft(value) 
...    self.rotate(index) 
... 
...  def insert(self, value): 
...    self._insert(bisect.bisect_left(self, value), value) 
... 
...  def __init__(self, iterable): 
...    super(FunkyDeque, self).__init__(sorted(iterable)) 
... 
>>> foo = FunkyDeque([3,2,1]) 
>>> foo 
deque([1, 2, 3]) 
>>> foo.insert(2.5) 
>>> foo 
deque([1, 2, 2.5, 3]) 

en cuenta que los requisitos de 1, 2, y 4 todos siguen directamente del hecho de que la estructura de datos subyacente es un deque, y el requisito 3 posee, debido a la forma en que se insertan los datos. (Nota por supuesto que se puede pasar por alto el requisito de ordenación llamando por ejemplo _insert, pero eso no viene al caso.)

Answer 3

blist.sortedlist

1. Cerca O (1) el rendimiento de como muchas de las cuatro operaciones siguientes.
2. Mantenimiento del orden ordenado al insertar un objeto en el contenedor.
3. Posibilidad de mirar el último valor (el valor más grande) contenido en el objeto.
4. Permitir saltos en ambos lados (obteniendo los valores más pequeños o más grandes).
5. Capacidad de obtener el tamaño total de o cantidad de objetos almacenados.
6. Al ser una solución preparada como el código en la biblioteca estándar de Python.

Es un árbol B +.