Pregunta sobre una solución de Google Python Class Day.

Hey, estoy tratando de aprender un poco sobre Python, así que decidí seguir el tutorial de Google. De todos modos tenía una pregunta sobre una de sus soluciones para un ejercicio.

Donde lo hice así.

# E. Given two lists sorted in increasing order, create and return a merged # list of all the elements in sorted order. You may modify the passed in lists. # Ideally, the solution should work in "linear" time, making a single # pass of both lists. def linear_merge(list1, list2): # +++your code here+++ return sorted(list1 + list2) 

Sin embargo lo hicieron de una manera más complicada. Entonces, ¿la solución de Google es más rápida? Como noté en las líneas de comentarios que la solución debería funcionar en un tiempo “lineal”, ¿cuál probablemente no sea la mía?

Esta es su solucion

 def linear_merge(list1, list2): # +++your code here+++ # LAB(begin solution) result = [] # Look at the two lists so long as both are non-empty. # Take whichever element [0] is smaller. while len(list1) and len(list2): if list1[0] < list2[0]: result.append(list1.pop(0)) else: result.append(list2.pop(0)) # Now tack on what's left result.extend(list1) result.extend(list2) return result 

El tuyo no es lineal, pero eso no significa que sea más lento. La complejidad algorítmica (“notación grande-oh”) a menudo es solo una guía aproximada y siempre solo cuenta una parte de la historia.

Sin embargo, el suyo tampoco es lineal, aunque puede parecer a primera vista. Para saltar de una lista es necesario mover todos los elementos posteriores, por lo tanto, hacer estallar desde el frente requiere mover todos los elementos restantes.

Es un buen ejercicio pensar cómo hacer esta O (n). Lo siguiente está en el mismo espíritu que la solución dada, pero evita sus trampas y generaliza a más de 2 listas por el ejercicio. Para exactamente 2 listas, podría eliminar el manejo del montón y simplemente probar qué elemento siguiente es más pequeño.

 import heapq def iter_linear_merge(*args): """Yield non-decreasing items from sorted a and b.""" # Technically, [1, 1, 2, 2] isn't an "increasing" sequence, # but it is non-decreasing. nexts = [] for x in args: x = iter(x) for n in x: heapq.heappush(nexts, (n, x)) break while len(nexts) >= 2: n, x = heapq.heappop(nexts) yield n for n in x: heapq.heappush(nexts, (n, x)) break if nexts: # Degenerate case of the heap, not strictly required. n, x = nexts[0] yield n for n in x: yield n 

En lugar del último if-for, la condición del bucle while podría cambiarse a solo “nexts”, pero probablemente vale la pena manejar especialmente el último iterador restante.

Si desea devolver estrictamente una lista en lugar de un iterador:

 def linear_merge(*args): return list(iter_linear_merge(*args)) 

¿Esto podría ser otra solución? #

  def linear_merge(list1, list2): tmp = [] while len(list1) and len(list2): #print list1[-1],list2[-1] if list1[-1] > list2[-1]: tmp.append(list1.pop()) else: tmp.append(list2.pop()) #print "tmp = ",tmp #print list1,list2 tmp = tmp + list1 tmp = tmp + list2 tmp.reverse() return tmp 

Con la mayoría de los datos ordenados, timsort se aproxima a lo lineal. Además, su código no tiene que andar con las listas. Por lo tanto, su código es posiblemente un poco más rápido.

Pero para eso es el momento, ¿no?

Creo que el problema aquí es que el tutorial ilustra cómo implementar un algoritmo conocido llamado ‘fusionar’ en Python. El tutorial no espera que realmente use una función de clasificación de biblioteca en la solución.

ordenado () es probablemente O (nlgn); entonces su solución no puede ser lineal en el peor de los casos.

Es importante entender cómo funciona merge () porque es útil en muchos otros algoritmos. Explota el hecho de que las listas de entrada se ordenan individualmente, moviéndose a través de cada lista secuencialmente y seleccionando la opción más pequeña. Los elementos restantes se adjuntan al final.

La pregunta no es cuál es “más rápido” para un caso de entrada dado, sino qué algoritmo es más complejo.

Existen variaciones híbridas de la combinación de ordenación que recurren a otro algoritmo de clasificación una vez que el tamaño de la lista de entrada cae por debajo de un cierto umbral.