Combinando dos listas ordenadas en Python

Tengo dos listas de objetos. Cada lista ya está ordenada por una propiedad del objeto que es del tipo datetime. Me gustaría combinar las dos listas en una lista ordenada. ¿Es la mejor manera solo de hacer una ordenación o hay una forma más inteligente de hacerlo en Python?

La gente parece estar sobre complicando esto … Simplemente combine las dos listas, luego ordénelas:

>>> l1 = [1, 3, 4, 7] >>> l2 = [0, 2, 5, 6, 8, 9] >>> l1.extend(l2) >>> sorted(l1) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

..o más corto (y sin modificar l1 ):

 >>> sorted(l1 + l2) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

..¡fácil! Además, utiliza solo dos funciones integradas, por lo que, si las listas son de un tamaño razonable, deberían ser más rápidas que implementar la clasificación / fusión en un bucle. Más importante aún, lo anterior es mucho menos código y es muy legible.

Si sus listas son grandes (más de unos pocos cientos de miles, supongo), puede ser más rápido usar un método de clasificación alternativo / personalizado, pero es probable que se realicen otras optimizaciones primero (por ejemplo, no almacenar millones de objetos de datetime )

Usando el timeit.Timer().repeat() (que repite las funciones 1000000 veces), lo comparé con la solución de ghoseb , y lo ordené sorted(l1+l2) es sustancialmente más rápido:

merge_sorted_lists tomó ..

 [9.7439379692077637, 9.8844599723815918, 9.552299976348877] 

sorted(l1+l2) tomó ..

 [2.860386848449707, 2.7589840888977051, 2.7682540416717529] 

¿Hay una manera más inteligente de hacer esto en Python?

Esto no se ha mencionado, así que seguiré adelante: hay una función de combinación de stdlib en el módulo heapq de python 2.6+. Si todo lo que buscas es hacer las cosas, esta podría ser una mejor idea. Por supuesto, si desea implementar el suyo propio, la fusión de la combinación de ordenación es el camino a seguir.

 >>> list1 = [1, 5, 8, 10, 50] >>> list2 = [3, 4, 29, 41, 45, 49] >>> from heapq import merge >>> list(merge(list1, list2)) [1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50] 

Aquí está la documentación .

En pocas palabras, a menos que len(l1 + l2) ~ 1000000 use:

 L = l1 + l2 L.sort() 

fusión contra comparación de clasificación

La descripción de la figura y el código fuente se puede encontrar aquí .

La figura fue generada por el siguiente comando:

 $ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin 

Esto es simplemente la fusión. Trate cada lista como si fuera una stack, y saque continuamente la más pequeña de las dos cabezas de stack, agregando el elemento a la lista de resultados, hasta que una de las stacks esté vacía. Luego agregue todos los elementos restantes a la lista resultante.

Hay un ligero defecto en la solución de ghoseb , por lo que es O (n ** 2), en lugar de O (n).
El problema es que esto se está realizando:

 item = l1.pop(0) 

Con listas o deques vinculados, esta sería una operación O (1), por lo que no afectaría la complejidad, pero como las listas de python se implementan como vectores, esto copia el rest de los elementos de l1 un espacio, una operación O (n) . Dado que esto se realiza cada paso a través de la lista, convierte un algoritmo O (n) en uno O (n ** 2). Esto se puede corregir utilizando un método que no altera las listas de fonts, sino que simplemente realiza un seguimiento de la posición actual.

He probado la evaluación comparativa de un algoritmo corregido frente a un ordenado simple (l1 + l2) según lo sugerido por dbr

 def merge(l1,l2): if not l1: return list(l2) if not l2: return list(l1) # l2 will contain last element. if l1[-1] > l2[-1]: l1,l2 = l2,l1 it = iter(l2) y = it.next() result = [] for x in l1: while y < x: result.append(y) y = it.next() result.append(x) result.append(y) result.extend(it) return result 

He probado estos con listas generadas con

 l1 = sorted([random.random() for i in range(NITEMS)]) l2 = sorted([random.random() for i in range(NITEMS)]) 

Para varios tamaños de lista, obtengo los siguientes tiempos (repitiendo 100 veces):

 # items: 1000 10000 100000 1000000 merge : 0.079 0.798 9.763 109.044 sort : 0.020 0.217 5.948 106.882 

Entonces, de hecho, parece que dbr tiene razón, es preferible usar ordenado () a menos que se esperen listas muy grandes, aunque tiene una complejidad algorítmica peor. El punto de equilibrio está en alrededor de un millón de artículos en cada lista de fonts (2 millones en total).

Sin embargo, una de las ventajas del enfoque de fusión es que es trivial volver a escribir como un generador, que usará sustancialmente menos memoria (sin necesidad de una lista intermedia).

[Editar] He reintentado esto con una situación más cercana a la pregunta: usando una lista de objetos que contienen un campo " date ", que es un objeto de fecha y hora. El algoritmo anterior se cambió para comparar con .date en .date lugar, y el método de clasificación se cambió a:

 return sorted(l1 + l2, key=operator.attrgetter('date')) 

Esto cambia las cosas un poco. El hecho de que la comparación sea más costosa significa que el número que realizamos se vuelve más importante, en relación con la velocidad constante de la implementación. Esto significa que la fusión crea el terreno perdido, superando el método sort () en lugar de 100,000 artículos. La comparación basada en un objeto aún más complejo (cadenas o listas grandes, por ejemplo) probablemente cambiaría este equilibrio aún más.

 # items: 1000 10000 100000 1000000[1] merge : 0.161 2.034 23.370 253.68 sort : 0.111 1.523 25.223 313.20 

[1]: Nota: En realidad, solo hice 10 repeticiones para 1,000,000 artículos y aumenté en consecuencia, ya que fue bastante lento.

Esta es una simple fusión de dos listas ordenadas. Eche un vistazo al siguiente código de muestra que combina dos listas ordenadas de enteros.

 #!/usr/bin/env python ## merge.py -- Merge two sorted lists -*- Python -*- ## Time-stamp: "2009-01-21 14:02:57 ghoseb" l1 = [1, 3, 4, 7] l2 = [0, 2, 5, 6, 8, 9] def merge_sorted_lists(l1, l2): """Merge sort two sorted lists Arguments: - `l1`: First sorted list - `l2`: Second sorted list """ sorted_list = [] # Copy both the args to make sure the original lists are not # modified l1 = l1[:] l2 = l2[:] while (l1 and l2): if (l1[0] <= l2[0]): # Compare both heads item = l1.pop(0) # Pop from the head sorted_list.append(item) else: item = l2.pop(0) sorted_list.append(item) # Add the remaining of the lists sorted_list.extend(l1 if l1 else l2) return sorted_list if __name__ == '__main__': print merge_sorted_lists(l1, l2) 

Esto debería funcionar bien con objetos de fecha y hora. Espero que esto ayude.

 from datetime import datetime from itertools import chain from operator import attrgetter class DT: def __init__(self, dt): self.dt = dt list1 = [DT(datetime(2008, 12, 5, 2)), DT(datetime(2009, 1, 1, 13)), DT(datetime(2009, 1, 3, 5))] list2 = [DT(datetime(2008, 12, 31, 23)), DT(datetime(2009, 1, 2, 12)), DT(datetime(2009, 1, 4, 15))] list3 = sorted(chain(list1, list2), key=attrgetter('dt')) for item in list3: print item.dt 

La salida:

 2008-12-05 02:00:00 2008-12-31 23:00:00 2009-01-01 13:00:00 2009-01-02 12:00:00 2009-01-03 05:00:00 2009-01-04 15:00:00 

Apuesto a que esto es más rápido que cualquiera de los sofisticados algoritmos de fusión de Python puro, incluso para datos grandes. Python 2.6’s heapq.merge es una historia completamente diferente.

La implementación de ordenación de Python “timsort” está específicamente optimizada para listas que contienen secciones ordenadas. Además, está escrito en C.

http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort

Como lo mencionó la gente, puede llamar a la función de comparación más veces por algún factor constante (¡pero tal vez, en muchos casos, llamarlo más veces en un período más corto!).

Sin embargo, nunca confiaría en esto. – Daniel Nadasi

Creo que los desarrolladores de Python están comprometidos a mantener el orden del tiempo, o al menos mantener un orden que sea O (n) en este caso.

Clasificación generalizada (es decir, separando las clasificaciones de radix de los dominios de valor limitado)
no se puede hacer en menos de O (n log n) en una máquina en serie. – Barry Kelly

Correcto, clasificar en el caso general no puede ser más rápido que eso. Pero como O () es un límite superior, la ordenación temporal es O (n log n) en una entrada arbitraria no contradice su clasificación O (n) dada (L1) + ordenada (L2).

La implementación recursiva está abajo. El rendimiento promedio es O (n).

 def merge_sorted_lists(A, B, sorted_list = None): if sorted_list == None: sorted_list = [] slice_index = 0 for element in A: if element <= B[0]: sorted_list.append(element) slice_index += 1 else: return merge_sorted_lists(B, A[slice_index:], sorted_list) return sorted_list + B 

o generador con complejidad de espacio mejorada:

 def merge_sorted_lists_as_generator(A, B): slice_index = 0 for element in A: if element <= B[0]: slice_index += 1 yield element else: for sorted_element in merge_sorted_lists_as_generator(B, A[slice_index:]): yield sorted_element return for element in B: yield element 
 def merge_sort(a,b): pa = 0 pb = 0 result = [] while pa < len(a) and pb < len(b): if a[pa] <= b[pb]: result.append(a[pa]) pa += 1 else: result.append(b[pb]) pb += 1 remained = a[pa:] + b[pb:] result.extend(remained) return result 

Una implementación del paso de fusión en Merge Sort que itera a través de ambas listas:

 def merge_lists(L1, L2): """ L1, L2: sorted lists of numbers, one of them could be empty. returns a merged and sorted list of L1 and L2. """ # When one of them is an empty list, returns the other list if not L1: return L2 elif not L2: return L1 result = [] i = 0 j = 0 for k in range(len(L1) + len(L2)): if L1[i] <= L2[j]: result.append(L1[i]) if i < len(L1) - 1: i += 1 else: result += L2[j:] # When the last element in L1 is reached, break # append the rest of L2 to result. else: result.append(L2[j]) if j < len(L2) - 1: j += 1 else: result += L1[i:] # When the last element in L2 is reached, break # append the rest of L1 to result. return result L1 = [1, 3, 5] L2 = [2, 4, 6, 8] merge_lists(L1, L2) # Should return [1, 2, 3, 4, 5, 6, 8] merge_lists([], L1) # Should return [1, 3, 5] 

Todavía estoy aprendiendo sobre algoritmos, por favor, hágame saber si el código podría mejorarse en algún aspecto, se agradece su opinión, ¡gracias!

Bueno, el enfoque ingenuo (combinar 2 listas en una grande y ordenar) será O (N * log (N)) de complejidad. Por otro lado, si implementa la fusión manualmente (no conozco ningún código listo en las librerías de Python para esto, pero no soy un experto) la complejidad será O (N), que es claramente más rápida. La idea se describe muy bien en el post por Barry Kelly.

Utilice el paso ‘fusionar’ de la ordenación de fusión, se ejecuta en tiempo O (n).

De wikipedia (pseudo-código):

 function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end while while length(left) > 0 append left to result while length(right) > 0 append right to result return result 

Si desea hacerlo de una manera más consistente con el aprendizaje de lo que ocurre en la iteración, intente esto

 def merge_arrays(a, b): l= [] while len(a) > 0 and len(b)>0: if a[0] < b[0]: l.append(a.pop(0)) else:l.append(b.pop(0)) l.extend(a+b) print( l ) 
 import random n=int(input("Enter size of table 1")); #size of list 1 m=int(input("Enter size of table 2")); # size of list 2 tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100 tb1.sort(); #sort the list 1 tb2.sort(); # sort the list 2 fus=[]; # creat an empty list print(tb1); # print the list 1 print('------------------------------------'); print(tb2); # print the list 2 print('------------------------------------'); i=0;j=0; # varialbles to cross the list while(i 

Se ha utilizado el paso de fusión de la ordenación de fusión. Pero he usado generadores . Complejidad del tiempo O (n)

 def merge(lst1,lst2): len1=len(lst1) len2=len(lst2) i,j=0,0 while(i 
 def compareDate(obj1, obj2): if obj1.getDate() < obj2.getDate(): return -1 elif obj1.getDate() > obj2.getDate(): return 1 else: return 0 list = list1 + list2 list.sort(compareDate) 

Se ordenará la lista en su lugar. Defina su propia función para comparar dos objetos, y pase esa función a la función de clasificación incorporada.

NO utilice el tipo de burbuja, tiene un rendimiento horrible.

Esta es mi solución en tiempo lineal sin editar l1 y l2:

 def merge(l1, l2): m, m2 = len(l1), len(l2) newList = [] l, r = 0, 0 while l < m and r < m2: if l1[l] < l2[r]: newList.append(l1[l]) l += 1 else: newList.append(l2[r]) r += 1 return newList + l1[l:] + l2[r:] 

Este código tiene una complejidad de tiempo O (n) y puede combinar listas de cualquier tipo de datos, dada una función de cuantificación como función de parámetro. Produce una nueva lista combinada y no modifica ninguna de las listas pasadas como argumentos.

 def merge_sorted_lists(listA,listB,func): merged = list() iA = 0 iB = 0 while True: hasA = iA < len(listA) hasB = iB < len(listB) if not hasA and not hasB: break valA = None if not hasA else listA[iA] valB = None if not hasB else listB[iB] a = None if not hasA else func(valA) b = None if not hasB else func(valB) if (not hasB or a 

Espero que esto ayude. Muy simple y directo:

l1 = [1, 3, 4, 7]

l2 = [0, 2, 5, 6, 8, 9]

l3 = l1 + l2

l3.sort ()

imprimir (l3)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]