print - sort values list python

Combinando dos listas ordenadas en Python

Question

Tengo dos listas de objetos. Cada lista ya está ordenada por una propiedad del objeto que es del tipo de fecha y hora. Me gustaría combinar las dos listas en una lista ordenada. ¿Es la mejor manera de hacer una especie o hay una forma más inteligente de hacer esto en Python?

Answer 1

¿Hay alguna forma más inteligente de hacer esto en Python?

Esto no se ha mencionado, así que continuaré - hay una función stdlib de fusión en el módulo heapq de Python 2.6+. Si todo lo que estás buscando hacer es hacer las cosas, esta podría ser una mejor idea. Por supuesto, si quiere implementar el suyo, la combinación de merge-sort 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 .

Answer 2

Bueno, el enfoque ingenuo (combinar 2 listas en grande y ordenar) será O (N * log (N)) 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 de Barry Kelly.

Answer 3

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]

Answer 4

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:]

Answer 5

Esto es simple fusión de dos listas ordenadas. Eche un vistazo al código de muestra a continuación que fusiona 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 los objetos de fecha y hora. Espero que esto ayude.

Answer 6

Esto simplemente se está fusionando. Trate cada lista como si fuera una pila, y estacione continuamente la cabeza de la pila más pequeña, agregando el elemento a la lista de resultados, hasta que una de las pilas esté vacía. A continuación, agregue todos los elementos restantes a la lista resultante.

Answer 7

Ha utilizado el paso de fusión del tipo de combinació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<len1 and j<len2):
if(lst1[i]<lst2[j]):
yield lst1[i]
i+=1
else:
yield lst2[j]
j+=1
if(i==len1):
while(j<len2):
yield lst2[j]
j+=1
elif(j==len2):
while(i<len1):
yield lst1[i]
i+=1
l1=[1,3,5,7]
l2=[2,4,6,8,9]
mergelst=(val for val in merge(l1,l2))
print(*mergelst)

Answer 8

Hay un pequeño defecto en ghoseb''s solución ghoseb''s , por lo que es O (n ** 2), en lugar de O (n).
El problema es que esto está funcionando:

item = l1.pop(0)

Con listas enlazadas o deques esto sería una operación O (1), por lo que no afectaría la complejidad, pero como las listas python se implementan como vectores, esto copia el resto de los elementos de l1 un espacio restante, una operación O (n) . Como esto se hace cada paso a través de la lista, convierte un algoritmo de O (n) en O (n ** 2). Esto puede corregirse utilizando un método que no altere las listas de origen, sino que simplemente haga un seguimiento de la posición actual.

dbr una 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

De hecho, parece que dbr es correcto, solo usar ordenado () es preferible a menos que esté esperando listas muy grandes, aunque tiene una complejidad algorítmica peor. El punto de equilibrio está en torno a un millón de elementos en cada lista de fuentes (2 millones en total).

Sin embargo, una ventaja del enfoque de fusión es que es trivial reescribir como un generador, que utilizará sustancialmente menos memoria (no es necesaria una lista intermedia).

[Editar] He vuelto a intentar esto con una situación más cercana a la pregunta - usando una lista de objetos que contiene 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. La comparación es más costosa y 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 compensa el terreno perdido, superando el método sort () en 100.000 elementos. La comparación basada en un objeto aún más complejo (grandes cadenas o listas, por ejemplo) probablemente cambiaría aún más este equilibrio.

# 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: De hecho, solo realicé 10 repeticiones para 1,000,000 de ítems y aumenté en consecuencia, ya que era bastante lento.

Answer 9

La gente parece estar 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, está utilizando solo dos funciones incorporadas, por lo que, suponiendo que las listas tengan un tamaño razonable, debería ser más rápido que implementar la ordenación / fusión en un bucle. Más importante aún, lo anterior es mucho menos código y muy legible.

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

Usando el timeit.Timer().repeat() (que repite las funciones 1000000 veces), lo puse en una comparación ghoseb''s solución ghoseb''s , y ghoseb''s 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]

Answer 10

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 las personas han mencionado, puede llamar a la función de comparación más veces por algún factor constante (¡pero tal vez lo llame más veces en un período más corto en muchos casos!).

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

Creo que los desarrolladores de Python se han comprometido a mantener timsort, o al menos mantener un tipo que sea O (n) en este caso.

Clasificación generalizada (es decir, dejar radix aparte ordena desde dominios de valor limitado)
no se puede hacer en menos de O (n log n) en una máquina serial. - Barry Kelly

Bien, clasificar en el caso general no puede ser más rápido que eso. Pero como O () es un límite superior, timsort es O (n log n) en una entrada arbitraria que no contradice su O (n) dado ordenado (L1) + ordenado (L2).

Answer 11

La implementación recursiva está debajo. 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 una 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

Answer 12

Larga historia corta, a menos que len(l1 + l2) ~ 1000000 use:

L = l1 + l2
L.sort()

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

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

Answer 13

Si quieres hacerlo de una manera más consistente con el aprendizaje de lo que sucede en la iteración prueba 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 )

Answer 14

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 avíseme si el código podría mejorarse en cualquier aspecto, sus comentarios son apreciados, ¡gracias!

Answer 15

Use el paso ''fusionar'' del tipo de fusión, se ejecuta en el tiempo O (n).

De en.wikipedia.org/wiki/Merge_sort (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

Answer 16

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)

Ordenará la lista en su lugar. Define tu propia función para comparar dos objetos y pasa esa función a la función de ordenamiento incorporada.

NO use sortear con burbujas, tiene un rendimiento horrible.

Answer 17

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

Answer 18

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 es más rápido que cualquiera de los sofisticados algoritmos de fusión puros de Python, incluso para datos de gran tamaño. El heapq.merge Python 2.6 es una historia completamente diferente.

Answer 19

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<n and j<m):
if(tb1[i]<tb2[j]):
fus.append(tb1[i]);
i+=1;
else:
fus.append(tb2[j]);
j+=1;
if(i<n):
fus+=tb1[i:n];
if(j<m):
fus+=tb2[j:m];
print(fus);
# this code is used to merge two sorted lists in one sorted list (FUS) without
#sorting the (FUS)