Ordenar los cortocircuitos

Question

Yo entiendo que:

head (map (2**) [1..999999])

Se evaluará en realidad sólo 2 ** 1, y ninguno de los demás, pero el libro que estoy leyendo dice que:

head (sort somelist)

Sólo tendrá que encontrar el elemento más pequeño de la lista, porque eso es todo lo que se usa. ¿Como funciona esto? Por lo que yo puedo decir, esto sería imposible con los algoritmos de ordenación que conozco (como la clasificación de la burbuja).

La única manera que puedo pensar que esto funcionaría es si el algoritmo de ordenación llegara a salir a través de toda la lista en busca de los elementos más pequeños, y luego recursivamente en la lista sin ese elemento. Para mí, esto suena muy lento.

¿Es así como funciona la función de clasificación, o hay otra algoritmo de ordenación no sé acerca, que permita un cortocircuito como es?

Answer 1

Este:

  

Sólo tendrá que encontrar el elemento más pequeño de la lista, porque eso es todo lo que se utiliza.

... en realidad debería decir que la función sólo tiene que hacer la cantidad mínima de trabajo que el algoritmo de ordenación requiere para encontrar el elemento más pequeño.

Por ejemplo, si estamos utilizando la clasificación rápida como nuestro algoritmo de clasificación subyacente, entonces head . quicksort es equivalente a la óptima algoritmo de selección conocido como ' Quickselect ', que es el peor caso lineal. Por otra parte, podemos implementar k -quickselect simplemente take k . quicksort.

Wikipedia señala en su artículo sobre los algoritmos de selección que (el subrayado es mío):

  

Debido soporte de idioma para la clasificación es más ubicuo, se prefiere el enfoque simplista de sorting seguido de indexación en muchos ambientes a pesar de su desventaja en la velocidad. En efecto, para los idiomas perezosos, este enfoque simplista puede incluso obtener la mejor complejidad posible que el k menor / mayor ordenados (con máximo / mínimo como un caso especial) si su tipo es lo suficientemente vago.

ordenación rápida funciona bien en este escenario, mientras que el orden predeterminado en Haskell (ordenamiento por mezcla) no compone tan bien, como lo hace trabajar más de lo estrictamente necesario para volver cada elemento de la lista ordenada. Como este puesto en la lista de correo Haskell señala:

  

quicksort perezoso es capaz de producir el lote de la   primero k elementos más pequeños en

     

O (n + k log k) tiempo total [1]

     

Si bien las necesidades mergesort perezosos

     

O (n + k log n) tiempo total [2]

Para más le gustaría leer más pequeña esta entrada del blog .

Answer 2

Si crea una función de comparación que tiene sus argumentos, como esta en la línea de comandos de GHCi:

> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y

A continuación se puede ver el comportamiento de sí mismo:

> sortBy myCompare "foobar"

"     Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
a     Cmp 'b' 'r'
b     Cmp 'f' 'o'
      Cmp 'f' 'r'
f     Cmp 'o' 'o'
      Cmp 'o' 'r'
o     Cmp 'o' 'r'
or"

Haskell está evaluando la cadena perezosamente, un carácter a la vez. se imprime la columna de la izquierda que se encuentra cada personaje, con la columna derecha de grabar las comparaciones requeridas, como impreso por "huella".

Tenga en cuenta que si se compila esto, especialmente con optimizaciones sobre, es posible obtener un resultado diferente. El optimizador ejecuta un analizador de rigurosidad que probablemente se dará cuenta de que toda la cadena se imprime, por lo que sería más eficiente para evaluar con avidez.

A continuación, intente

> head $ sortBy myCompare "foobar"

      Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
'a'

Si usted quiere entender cómo funciona esto, buscar el código fuente de la función de clasificación y evaluación de 'tipo 'foobar'' manualmente en papel.

qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
   where (less, greater) = partition (< x) xs

Entonces

   qsort ('f':"oobar")
 = qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
 = ("a" ++ "b") ++ "f" ++ qsort ('o':"or")

Y ahora hemos hecho lo suficiente para encontrar que 'a' es el primer elemento en el resultado sin tener que evaluar la otra llamada a "qsort". He omitido la comparación real debido a que su oculto dentro de la llamada a la "partición". En realidad "partición" también es perezosa, por lo que, de hecho, el argumento de la otra "qsort" no ha sido evaluada por lo que yo he mostrado a él.

Answer 3

El algoritmo que acaba de describir tiene un nombre específico: "ordenación por selección". Es O (n ² ) así que no es bastante lo más rápido que podía hacer. Sin embargo, si desea que los primeros elementos "k" en la matriz ordenada, la complejidad sería O (kn) que está bien si "k" es lo suficientemente pequeño (como su ejemplo).

Tenga en cuenta que está utilizando una función pura en un lenguaje funcional. El compilador es probable que sea capaz de generar código optimizado para sort en ambos casos observando la manera en que funciona se componen. Se puede inferir fácilmente que desea que el elemento mínimo cuando se redacta head y sort.