Implementación del algoritmo de ordenación más segura

Paso un tiempo implementando un algoritmo de solución rápida en C#. Después de terminar, comparé la velocidad de mi implementación y la Array.Sort-Method de C#.Implementación del algoritmo de ordenación más segura

Acabo de comparar la velocidad de trabajo en arreglos int aleatorios.

Aquí está mi aplicación:

static void QuickSort(int[] data, int left, int right) 
{ 
    int i = left - 1, 
     j = right; 

    while (true) 
    { 
     int d = data[left]; 
     do i++; while (data[i] < d); 
     do j--; while (data[j] > d); 

     if (i < j) 
     { 
      int tmp = data[i]; 
      data[i] = data[j]; 
      data[j] = tmp; 
     } 
     else 
     { 
      if (left < j) QuickSort(data, left, j); 
      if (++j < right) QuickSort(data, j, right); 
      return; 
     } 
    } 
}

Rendimiento (al ordenar un entero aleatorio [] con una longitud de 100 millones):
- mi algoritmo: 14.21 segundos
- .Net matriz <int> .Sort: 14.84 segundos

¿Alguien sabe cómo implementar mi a lgorithm incluso más rápido?
¿O alguien puede proporcionar una implementación más rápida (no es necesario que sea un servicio rápido) que mi ejecución más rápido?

Nota:
- por favor, no hay algoritmos que utilizan múltiples núcleos/procesadores para mejorar perrformance
- única fuente de C# válida código

voy a probar el rendimiento de los algoritmos proporcionados dentro de una unos minutos si estoy en línea

EDIT:
¿Cree que usar una red de clasificación ideal para piezas con menos de 8 valores mejoraría el rendimiento?

Fuente

2010-09-15 raisyn

intente repetir sus tiempos cuando una matriz ya está ordenada ... Luego, con una matriz que solo tiene dos elementos en el orden incorrecto ... –

Una ganancia de rendimiento del 4.3% - ¿Está haciendo esto por razones académicas? – flq

Ian tiene razón acerca de la matriz ya ordenada. Su elección de un elemento de pivote tendrá el peor rendimiento en el peor de los casos. Habiendo dicho eso, acelerar Quicksort es bastante sencillo. Seleccione un pivote mejor usando algo como el método MedianOfThree y use un algoritmo de clasificación más apropiado para particiones pequeñas. Supongo que está haciendo esto para investigación personal porque el método de clasificación de biblioteca del sistema es casi siempre la respuesta correcta. – Blastfurnace

¿Alguien sabe cómo implementar mi algoritmo aún más rápido?

Pude reducir el 10% del tiempo de ejecución convirtiendo el código para usar punteros.

public unsafe static void UnsafeQuickSort(int[] data) 
    { 
     fixed (int* pdata = data) 
     { 
      UnsafeQuickSortRecursive(pdata, 0, data.Length - 1); 
     } 
    } 

    private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right) 
    { 
     int i = left - 1; 
     int j = right; 

     while (true) 
     { 
      int d = data[left]; 
      do i++; while (data[i] < d); 
      do j--; while (data[j] > d); 

      if (i < j) 
      { 
       int tmp = data[i]; 
       data[i] = data[j]; 
       data[j] = tmp; 
      } 
      else 
      { 
       if (left < j) UnsafeQuickSortRecursive(data, left, j); 
       if (++j < right) UnsafeQuickSortRecursive(data, j, right); 
       return; 
      } 
     } 
    }

Fuente

2010-09-15 17:12:29

hay un pequeño error, pero realmente buena actualización (+1), ¡1,1 segundos más rápido en mi hardware! – raisyn

¿No está en conflicto con el requisito "seguro" en el título? – Gabe

Es un poco difícil de decir ... esto es lo suficientemente simple también ... Solo quería asegurarme de no obtener ningún código C/C++ altamente optimizado. – raisyn

La inserción binaria casi siempre gana para tiradas cortas (~ 10 elementos). A menudo es mejor que una red de clasificación ideal debido a la estructura simplificada de ramificación.

Dual pivot quicksort es más rápido que el quicksort. El documento vinculado contiene una implementación de Java que, presumiblemente, podría adaptarse.

Si solo está ordenando enteros, es probable que radix sort sea aún más rápido en arreglos largos.

Fuente

2010-09-15 17:29:09

Ese enlace ya no funciona. –

Eche un vistazo a Clases de corte y transposición de eventos extra: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html y http://home.westman.wave.ca/~rhenry/sort/.

Hay una implementación C# de Shear Sort aquí: http://www.codeproject.com/KB/recipes/cssorters.aspx.

Los ejemplos están en Java, pero está muy cerca de C#. Son géneros paralelos porque funcionan más rápido en múltiples núcleos, pero aún así deberían ser muy rápidos.

Fuente

2010-09-15 19:49:54

Este primer (y probablemente el segundo) algoritmo de ordenación rápida se rompe al ordenar matrices con elementos duplicados. Usé this uno, que funciona bien.

Fuente

2011-01-11 13:55:25

Implementación del algoritmo de ordenación más segura

Respuesta

Cuestiones relacionadas