¿Puedo crear una lista y ordenarla al mismo tiempo?

Question

Estoy trabajando en un script para una pieza de software, y realmente no me da acceso directo a los datos que necesito. En cambio, necesito pedir cada información que necesito y crear una lista de los datos que obtengo. Por diversas razones, necesito que se ordene la lista. Es muy fácil construir la lista una sola vez, y luego ordenarla, seguido de hacer cosas con ella. Sin embargo, supongo que sería más rápido ejecutar todo una vez, en lugar de compilar la lista y luego ordenarla.

Así, en el momento en que he básicamente tengo esto:

my_list = [] 

for item in "query for stuff": 
    my_list.append("query for %s data" % item) 

my_list.sort() 

do_stuff(my_list) 

El bit de "consulta de cosas" es la interfaz de consulta con el software, que me dará un iterable. my_list necesita contener una lista de datos de los contenidos de dicho iterable. Al hacerlo así, consulto la primera lista y luego la recorro para extraer los datos y ponerlos en my_list. Entonces lo estoy ordenando. Por último, le estoy haciendo cosas con el método do_stuff(), que lo recorrerá y hará cosas para cada elemento.

El problema es que no puedo do_stuff() antes de que esté ordenado, ya que el orden de la lista es importante por varias razones. No creo que pueda evitar tener que pasar dos listas: una para construir la lista y una para hacer cosas para cada elemento, ya que no sabremos por adelantado si un artículo agregado recientemente en la posición N Quédese en la posición N después de que hayamos agregado el siguiente elemento, pero parece más limpio insertar cada elemento de forma ordenada, en lugar de agregarlos al final. Algo así como esto:

for item in "query for stuff": 
    my_list.append_sorted(item) 

¿Vale la pena molestarse tratando de hacerlo de esta manera, o debería sólo se adhieren a la construcción de la lista y, a continuación, la clasificación es?

Gracias!

Answer 1

La respuesta corta es: no vale la pena.

Eche un vistazo a insertion sort. El peor tiempo de ejecución es O(n^2) (el promedio de casos también es cuadrático). Por otro lado, Python's sort (también conocido como Timsort) tomará O(n log n) en el peor de los casos.

Sí, "parece" más limpio mantener la lista ordenada mientras inserta, pero eso es una falacia. No hay un beneficio real para él. La única vez que consideraría usar la ordenación por inserción es cuando necesita mostrar la lista ordenada después de cada inserción.

Answer 2

Los dos enfoques son asintóticamente equivalentes.

La ordenación es O (n lg n) (Python usa Timsort por defecto, excepto en arreglos muy pequeños), y la inserción en una lista ordenada es O (lg n) (usando búsqueda binaria), lo que debería hacer n veces

En la práctica, un método u otro puede ser un poco más rápido, dependiendo de la cantidad de datos que ya está ordenada.

EDIT: I asumido que la inserción en el medio de una lista ordenada después de que haya encontrado el punto de inserción sería constante de tiempo (es decir, la lista se comportó como una lista enlazada, que es la estructura de datos lo haría usar para tal algoritmo). Este probablemente no es el caso con las listas de Python, como lo señala Sven. Esto haría que el enfoque "mantener ordenada la lista" sea O (n^2), es decir, tipo de inserción.

Digo "probablemente" porque algunas implementaciones de lista cambian de una matriz a una lista vinculada a medida que la lista crece, el ejemplo más notable es CFArray/NSArray en CoreFoundation/Cocoa. Este puede o no ser el caso con Python.

Answer 3

Eche un vistazo al módulo bisect. Le brinda varias herramientas para mantener un orden de lista. En su caso, es probable que desee utilizar bisect.insort.

for item in query_for_stuff(): 
    bisect.insort(my_list, "query for %s data" % item)