haskell - ordenamiento - Complejidad del tiempo de pseudo-quicksort

quicksort ventajas y desventajas

Question

Sé que el quicksort tiene una complejidad de tiempo promedio O(n log n) . Un pseudo-quicksort (que es solo un quicksort cuando se mira desde lo suficientemente lejos, con un nivel de abstracción adecuadamente alto) que se usa a menudo para demostrar la concisión de los lenguajes funcionales es el siguiente (dado en Haskell):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

De acuerdo, entonces sé que esto tiene problemas. El mayor problema con esto es que no se ordena en su lugar, lo que normalmente es una gran ventaja de la oferta rápida. Incluso si eso no importara, aún tomaría más tiempo que una solución rápida típica porque tiene que hacer dos pasadas de la lista cuando la divide, y agrega operaciones costosas para volver a unirlas después. Además, la elección del primer elemento como pivote no es la mejor opción.

Pero incluso teniendo en cuenta todo eso , ¿no es la complejidad del tiempo promedio de este servicio rápido la misma que la del servicio rápido estándar? A saber, O(n log n) ? Porque los añadidos y la partición aún tienen complejidad de tiempo lineal, incluso si son ineficientes.

Answer 1

Estoy de acuerdo con su suposición de que la complejidad de tiempo promedio todavía es O(n log n) . No soy un experto y estoy 100% seguro, pero estos son mis pensamientos:

Este es un pseudo código del quicksort in situ: (llame a quicksort con l = 1 yr = longitud de la matriz)

Quicksort(l,r)  
--------------
IF r-l>=1 THEN  
    choose pivot element x of {x_l,x_l+1,...,x_r-1,x_r}   
    order the array-segment x_l,...x_r in such a way that  
        all elements < x are on the left side of x // line 6  
        all elements > x are on the right side of x // line 7  
    let m be the position of x in the ''sorted'' array (as said in the two lines above)  
    Quicksort(l,m-1);  
    Quicksort(m+1,r)  
FI  

El análisis de complejidad de tiempo promedio razona entonces seleccionando las comparaciones "<" en la línea 6 y 7 como la operación dominante en este algoritmo y finalmente llega a la conclusión de que la complejidad de tiempo promedio es O (n log n). Como el costo de la línea "ordene el segmento-matriz x_l, ... x_r de tal manera que ..." no se tengan en cuenta (solo la operación dominante es importante en el análisis de complejidad de tiempo si desea encontrar límites), creo "porque tiene que hacer dos pasadas de la lista cuando la particiona" no es un problema, ya que su versión de Haskell tomaría aproximadamente el doble de tiempo en este paso. Lo mismo se aplica a la operación apéndice y estoy de acuerdo con que esto no agrega nada a los costos asintóticos:

Porque los añadidos y la partición aún tienen complejidad de tiempo lineal, incluso si son ineficientes.

En aras de la conveniencia, supongamos que esto suma "n" a nuestros costos de complejidad de tiempo, de modo que tenemos "O (n log n + n)". Como existe un número natural o para ese n log n> n para todos los números naturales mayores que o, es cierto que puede estimar n log n + n arriba 2 n log n y abajo n n log n, por lo tanto n log n + n = O (n log n).

Además, la elección del primer elemento como pivote no es la mejor opción.

Creo que la elección del elemento pivote es irrelevante aquí, porque en el análisis promedio de casos se supone una distribución uniforme de los elementos en el conjunto. No puede saber desde qué lugar del conjunto debe seleccionarlo, y por lo tanto debe considerar todos estos casos en los que su elemento pivote (independientemente de qué lugar de la lista lo tome) es el elemento más pequeño. de tu lista, para i = 1 ... r.

Answer 2

No sé cuánto mejora esto la complejidad del tiempo de ejecución, pero al usar un acumulador puede evitar los costosos (++) :

quicksort xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)

Answer 3

Este "quicksort" es en realidad un tipo de árbol deforestado: http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell

data Tree a = Leaf | Node a (Tree a) (Tree a)

mkTree [] = Leaf
mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs))

El árbol binario está desequilibrado, por lo que O (N ^ 2) en el caso más desfavorable y O (N * Log N) la complejidad del caso medio para generar el árbol de búsqueda.

foldTree f g Leaf = g
foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r)

treeSort l = foldTree (/x lft rht -> lft++[x]++rht) [] (mkTree l)

El algoritmo de recuperación tiene el O (N ^ 2) peor caso y O (N * Log N) la complejidad del caso promedio.

Bien equilibrado

Prelude> let rnds = iterate step where step x = (75*x) `mod` 65537
Prelude> length . quicksort . take 4000 . rnds $ 1
4000
(0.08 secs, 10859016 bytes)
Prelude> length . quicksort . take 8000 . rnds $ 1
8000
(0.12 secs, 21183208 bytes)
Prelude> length . quicksort . take 16000 . rnds $ 1
16000
(0.25 secs, 42322744 bytes)

No tan bien equilibrado:

Prelude> length . quicksort . map (`mod` 10) $ [1..4000]
4000
(0.62 secs, 65024528 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..8000]
8000
(2.45 secs, 241906856 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..16000]
16000
(9.52 secs, 941667704 bytes)

Answer 4

Busque aquí un quicksort verdadero O (n log n) que funcionará tanto en matrices como en listas: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.23.4398&rep=rep1&type=pdf Es es bastante fácil de implementar en Common Lisp y supera la implementación de sortear de muchos cefaleas comerciales.

Answer 5

Sí, esta versión tiene la misma complejidad asintótica que la versión clásica: reemplaza la partition tiempo lineal con: dos pasadas ( < y >= ) y tiene el tiempo lineal adicional ++ (que incluye redistribución lineal) /proceso de copiar). Entonces es un factor constante fuerte peor que una partición local, pero sigue siendo lineal. Todos los demás aspectos del algoritmo son los mismos, por lo que el mismo análisis que da O (n log n) average-case para el "verdadero" (es decir, en el lugar) quicksort todavía se mantiene aquí.

Answer 6

Puedo ofrecerle una prueba de tiempo de ejecución en Ideone.com que parece mostrar tiempos de ejecución más o menos lineal para las versiones basadas en (++) y la que utiliza la técnica de acumulador de la respuesta de Landei , así como otra utilizando una -pasar la partición de tres vías . En datos ordenados , esto se vuelve cuadrático o peor para todos ellos.

-- random:   100k        200k         400k         800k
-- _O    0.35s-11MB  0.85s-29MB   1.80s-53MB   3.71s-87MB   n^1.3  1.1  1.0
-- _P    0.36s-12MB  0.80s-20MB   1.66s-45MB   3.76s-67MB   n^1.2  1.1  1.2
-- _A    0.31s-14MB  0.62s-20MB   1.58s-54MB   3.22s-95MB   n^1.0  1.3  1.0
-- _3    0.20s- 9MB  0.41s-14MB   0.88s-24MB   1.92s-49MB   n^1.0  1.1  1.1

-- ordered:   230     460     900     1800
-- _P        0.09s   0.33s   1.43s    6.89s                 n^1.9  2.1  2.3
-- _A        0.09s   0.33s   1.44s    6.90s                 n^1.9  2.1  2.3
-- _3        0.05s   0.15s   0.63s    3.14s                 n^1.6  2.1  2.3

quicksortO xs = go xs  where
  go []  =  []
  go (x:xs) = go [y | y<-xs, y<x] ++ [x] ++ go [y | y<-xs, y>=x]

quicksortP xs = go xs  where
  go []  =  []
  go (x:xs) = go [y | y<-xs, y<x] ++ (x : go [y | y<-xs, y>=x])

quicksortA xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)

quicksort3 xs = go xs [] where
  go     (x:xs) zs = part x xs zs [] [] []
  go     []     zs = zs
  part x []     zs a b c = go a ((x : b) ++ go c zs)
  part x (y:ys) zs a b c =
      case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

Las complejidades empíricas del tiempo de ejecución se estiman aquí como O(n^a) donde a = log( t2/t1 ) / log( n2/n1 ) . _{Los tiempos son muy aproximados ya que los ideone no son muy confiables con ocasionales outlyers lejanos, pero para verificar la complejidad del tiempo es suficiente.}

Por lo tanto, estos datos parecen indicar que la partición de un solo paso es más rápida en 1.5x-2x que los esquemas de dos pasos, y que el uso (++) de ninguna manera ralentiza las cosas, en absoluto . Es decir, las "operaciones de adición" no son "costosas" en absoluto. El comportamiento cuadrático o (++) / append parece ser un mito urbano, en el contexto de Haskell, por supuesto ( edit: ... es decir, en el contexto de recursión guardada / módulo de recursión de cola ; véase esta respuesta ) ( actualización: como usuario: AndrewC explica que es muy real con el plegado a la izquierda, lineal cuando (++) se usa con el plegado correcto, más sobre esto aquí y aquí ).