La construcción de la clasificación rápida con php

Question

Hace poco leí acerca de la clasificación rápida y se preguntaba si sería inteligente para construir mi propia función para ordenar las cosas con la clasificación rápida o si sería inefficent. ¿Qué opinas es el construido en el tipo funciona mejor que una función autoconstruidas clasificación rápida?

Answer 1

http://php.net/sort

  

Nota: Como la mayoría de clasificación de PHP   funciones, sort () utiliza una   implementación de »ordenación rápida.

Las funciones básicas de PHP 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 es más rápido que escribir su propia, pero supongo que estos serían cuando se tiene un caso muy específico y usted puede hacer sus propias optimizaciones específicas para ello. Creo que es poco probable que sea el caso aquí.

Answer 2

De hecho lo hice para un punto de datos en una presentación que estoy poniendo juntos. La prueba ordena una matriz de 250.000 números enteros usando la función de clasificación nativa y una implementación del algoritmo de ordenación rápida escrito en PHP. El contenido de la matriz son exactamente los mismos para ambas carreras, los datos es aleatorio, y el tiempo indicado es sólo para realizar la clasificación, no otro procesamiento necesario invocar el 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 de 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

En particular, Chrome y Safari realiza más más rápido para la prueba de JavaScript, pero no incluyo los que están aquí porque esas pruebas se registraron en un entorno diferente.

Answer 3

Seguir con la función de clasificación incorporado. Quicksort es un algoritmo simple, pero para obtener un buen rendimiento en los equipos que están realmente en uso requiere un poco de finura. Es más que probable que la función incorporada ya está más optimizado que cualquier cosa que iba a escribir en una cantidad razonable de tiempo. (El aumento de velocidad constante del factor de ser escrito en C en lugar de PHP también es probablemente útil.)

Si está ordenando tantos elementos que se retrasan por la función de clasificación, es probable que 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 4

Como referencia hay una aplicación PHP aquí:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting / ordenación rápida # PHP

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 cambiarán de posición al azar, incluso entre diferentes carreras. Asombroso que el código puede producir un orden diferente utilizando los mismos datos una y otra vez. Al final tuve que poner en práctica mi propia ordenación rápida para eliminar esta anomalía.

Answer 6

Sólo por diversión, aquí es una versión en el lugar de la clasificación rápida en PHP que se me ocurrió. El truco aquí es pasar el array a ordenar 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);
}

Answer 7

A continuación la clase para implementar la Ordenación rápida en PHP -

            <?php
            class quickSort{
            /* low  --> Starting index,  high  --> Ending index */
                public $arr;
                public function __construct($arr){
                    $this->arr = $arr;
                }
                public function qsort($low,$high){
                    if($low===null || $high===null){    
                        return false;
                    }
                    if($low < $high){           
                        $pi = $this->partition($low,$high);
                        $this->qsort($low,$pi-1); /*before pivot*/
                        $this->qsort($pi+1,$high); /*before pivot*/
                    }
                }

                /* This function takes last element as pivot, places
                   the pivot element at its correct position in sorted
                    array, and places all smaller (smaller than pivot)
                   to left of pivot and all greater elements to right
                   of pivot */
                public function partition($low,$high){
                    if($low===null || $high===null){
                        return false;
                    }
                    $pivot = $this->arr[$high];
                    $i = $low-1; /*index of smaller element*/

                    for($j = $low; $j <= $high-1; $j++)
                    {
                        // If current element is smaller than or equal to pivot

                        if($this->arr[$j] <= $pivot)
                        {
                            $i++;    // increment index of smaller element
                            $this->swap($i,$j);         
                        }
                    }
                    //swap arr[i + 1] and arr[high])
                    $this->swap($i+1,$high);

                    return $i+1;    
                }

                public function swap($i,$j){
                    $p=$this->arr[$i];
                    $q=$this->arr[$j];
                    $this->arr[$i]=$q;
                    $this->arr[$j]=$p;      
                }
            }
            $arr = array(10, 80, 30, 90, 40, 50, 70);
            $obj = new quickSort($arr);
            $obj->qsort(0,6);
            print_r($obj->arr);


            ?>