Construcción de quicksort con php

Question

Recientemente leí sobre quicksort y me preguntaba si sería inteligente crear mi propia función para ordenar cosas con quicksort o si sería ineficaz. ¿Cuál cree que es la función de ordenamiento incorporada mejor que una función de quicksort autoconstruida?

Answer 1

De http://php.net/sort

Nota : Como la mayoría de las funciones de clasificación PHP , sort() utiliza una implementación de »Quicksort.

funciones PHP

el núcleo serán implementados en C, en lugar de PHP, por lo que generalmente deben ser significativamente más rápido que cualquier cosa que usted mismo puede escribir en PHP. Habrá casos en los que sea más rápido escribir uno propio, pero supongo que esto sería cuando tienes un caso muy específico y puedes hacer tus propias optimizaciones específicas para eso. Creo que es poco probable que sea el caso aquí.

Answer 2

Se pega con la función de clasificación incorporada. Quicksort es un algoritmo simple, pero para obtener un buen rendimiento en las computadoras que realmente están en uso se requiere un poco de delicadeza. Es más que probable que la función incorporada ya esté más optimizada que cualquier cosa que escribiría en un período de tiempo razonable. (La aceleración de factor constante por estar escrita en C en lugar de PHP también es útil).

Si está ordenando tantos elementos que la función de clasificación le ralentiza, probablemente esté haciendo algo mal. (Esto es PHP después de todo. Usted debe usar un lenguaje de propósito general para el procesamiento de datos intensivos. Será más fácil escribir el código, y se ejecutará más rápido.)

Answer 3

De hecho, hice esto para obtener un punto de datos sobre una presentación que estoy reuniendo. La prueba ordena una matriz de 250,000 enteros utilizando la función de clasificación nativa y una implementación del algoritmo de quicksort escrito en php. El contenido de la matriz es exactamente el mismo para ambas ejecuciones, los datos se asignan al azar, y la hora informada es solo para realizar el ordenamiento, no otro procesamiento necesario para invocar al intérprete de php.

Resultados:

 
    Native sort implementation: 1.379 seconds 
PHP quicksort implementation: 30.615 seconds 

Definitivamente el uso de la aplicación nativa. Ese debería ser el caso para cualquier lenguaje interpretado.

Los resultados para los otros idiomas que probé con las mismas condiciones utilizando la misma aplicación en el mismo hardware y el sistema operativo, proporcionan una comparación de rendimiento interesante y poner el resultado de PHP en perspectiva:

 
       C: 0.107 seconds 
      Java: 0.250 seconds 
JavaScript (FF3): 4.401 seconds 

Notablemente, cromo y Safari realizó mucho más rápido para la prueba de JavaScript, pero no los incluyo aquí porque esas pruebas se grabaron en un entorno diferente.

Answer 4

Como referencia hay una aplicación PHP aquí:

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort#C.23

Answer 5

Una cosa acerca de la clase php rápida (asort, arsort, etc) es que echan a perder sus valores iguales, es decir, que los valores con diferentes teclas intercambiará la posición al azar, incluso entre diferentes ejecuciones. Sorprende que el código pueda producir un orden diferente usando los mismos datos una y otra vez. Al final tuve que implementar mi propia clasificación rápida para eliminar esta anomalía.

Answer 6

Simplemente por diversión, he aquí una versión local de quicksort en PHP que se me ocurrió. El truco aquí es pasar la matriz para ordenarla como referencia.

function partition(&$arr,$leftIndex,$rightIndex) 
{ 
    $pivot=$arr[($leftIndex+$rightIndex)/2]; 

    while ($leftIndex <= $rightIndex) 
    {   
     while ($arr[$leftIndex] < $pivot)    
       $leftIndex++; 
     while ($arr[$rightIndex] > $pivot) 
       $rightIndex--; 
     if ($leftIndex <= $rightIndex) { 
       $tmp = $arr[$leftIndex]; 
       $arr[$leftIndex] = $arr[$rightIndex]; 
       $arr[$rightIndex] = $tmp; 
       $leftIndex++; 
       $rightIndex--; 
     } 
    } 
    return $leftIndex; 
} 

function quickSort(&$arr, $leftIndex, $rightIndex) 
{ 
    $index = partition($arr,$leftIndex,$rightIndex); 
    if ($leftIndex < $index - 1) 
     quickSort($arr, $leftIndex, $index - 1); 
    if ($index < $rightIndex) 
     quickSort($arr, $index, $rightIndex); 
}