¿Python tiene una lista ordenada?

Con lo cual me refiero a una estructura con:

• O (log n) complejidad para x.push()operaciones
• O (log n) complejidad para encontrar un elemento
• O (n) complejidad para calcular list(x)que se ordenará

También tenía una pregunta relacionada sobre el rendimiento list(...).insert(...)que ahora está aquí .

La lista estándar de Python no está ordenada de ninguna forma. El módulo heapq estándar se puede usar para agregar O (log n) a una lista existente y eliminar el más pequeño de O (log n), pero no es una lista ordenada en su definición.

Existen varias implementaciones de árboles equilibrados para Python que satisfagan sus necesidades, por ejemplo rbtree , RBTree o pyavl .

¿Hay alguna razón particular para sus requisitos de Big-O? ¿O simplemente quieres que sea rápido? El módulo sortedcontainers es Python puro y rápido (como en implementaciones rápidas como C como blist y rbtree).

La comparación de rendimiento muestra los puntos de referencia más rápido o a la par con el tipo de lista ordenada de blist. Tenga en cuenta también que rbtree, RBTree y PyAVL proporcionan dict ordenados y establecen tipos, pero no tienen un tipo de lista ordenada.

Si el rendimiento es un requisito, recuerde siempre hacer una referencia. Un módulo que corrobore la afirmación de ser rápido con la notación Big-O debe ser sospechoso hasta que también muestre comparaciones de referencia.

Descargo de responsabilidad: soy el autor del módulo de contenedores ordenados de Python.

Instalación:

pip install sortedcontainers

Uso:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5

Aunque todavía nunca he verificado las velocidades de "gran O" de las operaciones básicas de la lista de Python, el bisectmódulo estándar probablemente también valga la pena mencionar en este contexto:

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PD. Ah, lo siento, bisectse menciona en la pregunta de referencia. Aún así, creo que no será mucho daño si esta información está aquí)

PPS Y las listas de CPython son en realidad matrices (no, digamos, listas de omisión o etc.). Bueno, supongo que tienen que ser algo simple, pero en cuanto a mí, el nombre es un poco engañoso.

Entonces, si no me equivoco, las velocidades de bisección / lista probablemente serían:

• para un push (): O (n) para el peor de los casos;
• para una búsqueda: si consideramos que la velocidad de indexación de matriz es O (1), la búsqueda debe ser una operación O (log (n));
• para la creación de la lista: O (n) debe ser la velocidad de la copia de la lista; de lo contrario, es O (1) para la misma lista)

Upd. Después de una discusión en los comentarios, permítanme vincular aquí estas preguntas SO: ¿Cómo se implementa la lista de Python y cuál es la complejidad del tiempo de ejecución de las funciones de la lista de Python?

import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)

Aunque (todavía) no proporciona una función de búsqueda personalizada, el heapqmódulo puede satisfacer sus necesidades. Implementa una cola de montón utilizando una lista regular. Tendría que escribir su propia prueba de membresía eficiente que haga uso de la estructura interna de la cola (eso se puede hacer en O (log n) , yo diría ...). Hay un inconveniente: extraer una lista ordenada tiene complejidad O (n log n) .

Yo usaría los módulos biscecto sortedcontainers. Realmente no tengo experiencia, pero creo que el heapqmódulo funciona. Contiene unHeap Queue

Puede que no sea difícil implementar su propia lista de clasificación en Python. A continuación se muestra una prueba de concepto:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= Resultados ============

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

101

3

50