print - sort python 3

¿Python tiene una lista ordenada?

Question

Con lo cual me refiero a una estructura con:

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

También tuve una pregunta relacionada con el rendimiento de list(...).insert(...) que ahora está here .

Answer 1

¿Hay alguna razón particular para tus requerimientos de O grande? ¿O solo quieres que sea rápido? El módulo sortedcontainers es puro-Python 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 tipos de dict y set ordenados pero no tienen un tipo de lista ordenada.

Si el rendimiento es un requisito, siempre recuerde compararlo. 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 Python sortedcontainers.

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

Answer 2

Aunque todavía no he comprobado las velocidades de "O grande" de las operaciones básicas de la lista de Python, probablemente valga la pena mencionar el módulo estándar bisect 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, bisect se menciona en la pregunta a la que se hace referencia. Aún así, creo que no habrá mucho daño si esta información estará aquí)

PPS. Y las listas de CPython son en realidad matrices (no, por ejemplo, skiplists, 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 la indexación de matrices 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. Tras una discusión en los comentarios, permítanme unir aquí estas preguntas SO: ¿Cómo se implementa Python''s List y cuál es la complejidad de tiempo de ejecución de las funciones de la lista de Python?

Answer 3

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

Answer 4

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

Existen varias implementaciones de árboles balanceados para Python que cumplen con sus requisitos, por ejemplo, RBTree , pyavl o pyavl .

Answer 5

Puede que no sea difícil implementar su propia lista de clasificación en Python. A continuación hay 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

Answer 6

Yo usaría los módulos biscect o sortedcontainers . Realmente no tengo experiencia, pero creo que el módulo heapq funciona. Contiene una Heap Queue

Answer 7

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