C# merge sort performance

Question

solo una nota rápida, esto no es tarea. Solo estoy tratando de repasar mis algoritmos. Estoy jugando con mergesort en C# y he escrito un método recursivo que puede clasificar en base a los genéricos:

class SortAlgorithms 
{ 

    public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T> 
    { 
     T[] left, right; 
     int middle = unsortedArray.Length/2; 

     left = new T[middle]; 
     right = new T[unsortedArray.Length - middle]; 

     if (unsortedArray.Length <= 1) 
      return unsortedArray; 

     for (int i = 0; i < middle; i++) 
     { 
      left[i] = unsortedArray[i]; 
     } 

     for (int i = middle; i < unsortedArray.Length; i++) 
     { 
      right[i - middle] = unsortedArray[i]; 
     } 

     left = MergeSort(left); 

     right = MergeSort(right); 


     return Merge<T>(left, right); 
    } 

    private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T> 
    { 
     T[] result = new T[left.Length + right.Length]; 

     int currentElement = 0; 

     while (left.Length > 0 || right.Length > 0) 
     { 
      if (left.Length > 0 && right.Length > 0) 
      { 
       if (left[0].CompareTo(right[0]) < 0) 
       { 
        result[currentElement] = left[0]; 
        left = left.Skip(1).ToArray(); 
        currentElement++; 
       } 
       else 
       { 
        result[currentElement] = right[0]; 
        right = right.Skip(1).ToArray(); 
        currentElement++; 
       } 
      } 
      else if (left.Length > 0) 
      { 
       result[currentElement] = left[0]; 
       left = left.Skip(1).ToArray(); 
       currentElement++; 
      } 
      else if (right.Length > 0) 
      { 
       result[currentElement] = right[0]; 
       right = right.Skip(1).ToArray(); 
       currentElement++; 
      } 
     } 

     return result; 
    } 
} 

Esto funciona, pero es muy lento. He usado System.Diagnostic.StopWatch para verificar el rendimiento en comparación con Array.Sort (que usa el algoritmo QuickSort) para compararlo con mi MergeSort y la diferencia es tan significativa que me pregunto si tal vez estoy implementando esto incorrectamente. ¿Algún comentario?

Answer 1

No soy un programador C#, pero ¿podría ser el problema el uso de declaraciones como esta?

left = left.Skip(1).ToArray(); 

Esto podría implementarse de forma que fuerce una copia profunda de la matriz subyacente. Si es así, esto reduciría el rendimiento de la combinación de O (n) a O (n), inmediatamente cayendo el rendimiento de la clasificación de fusión resultante de O (n log n) a O (n).

(Esto se debe a los cambios de recurrencia de

T (1) = O (1)

T (n) ≤ 2T (n/2) + O (n)

que tiene solución T (n) = O (n log n), para

T (1) = O (1)

T (n) ≤ 2T (n/2) + O (n)

que tiene solución T (n) = O (n).)

Answer 2

Asigna memoria constantemente en forma de matrices intermedias. Piensa en la dirección de reutilizar la matriz original.

Answer 3

Como las otras dos respuestas han dicho, estás creando nuevas matrices en todo el lugar, gastando mucho tiempo y memoria en eso (supongo, la mayor parte de tu tiempo y casi todo el uso de tu memoria).

Una vez más, añadiría que todo lo demás es igual recursión tiende a ser más lenta que la iteración, y utilizar más espacio de pila (tal vez incluso causar desbordamiento con un problema lo suficientemente grande, donde la iteración no).

Sin embargo. Merge-sort se presta bien al enfoque de múltiples subprocesos, ya que puede tener diferentes subprocesos que manejan diferentes partes del primer lote de particiones.

Por lo tanto, si se me jugando con esto, mis próximos dos experimentos serían:

1. Para el primer bit de la partición, en lugar de llamar MergeSort de forma recursiva, me gustaría lanzar un nuevo hilo hasta una vez que tenía un hilo por ejecución central (si debería hacerlo por núcleo físico o núcleo virtual en el caso de hyperthreading, es algo con lo que experimentaría).
2. Hecho esto, trataría de volver a escribir el método recursivo para hacer lo mismo sin llamadas recursivas.

Después de la materia ToArray() se ha tratado de ver cómo un enfoque multi-hilo que primero dividir el trabajo entre un número óptimo de núcleos, y luego tuvo cada núcleo haga su trabajo de forma iterativa, podría ser bastante interesante.

Answer 4

En primer lugar, aquí hay un enlace a una solución optimizada a una pregunta similar: Java mergesort, should the "merge" step be done with queues or arrays?

Su solución es lenta porque estás asignar repetidamente nuevas subseries. La asignación de memoria es mucho más costosa que la mayoría de las otras operaciones (tiene un costo de asignación, un costo de recopilación y una pérdida de localidad de caché). Normalmente no es un problema, pero si estás intentando codificar una rutina de clasificación estricta, entonces es importante. Para ordenar por fusión, solo necesita una matriz de destino y una matriz temporal.

Hilos de bifurcación para paralelizar todavía son órdenes de magnitud más caros que eso. Así que no te muevas a menos que tengas una gran cantidad de datos para ordenar.

Como menciono en la respuesta anterior, una forma de acelerar su clasificación de fusión es aprovechar el orden existente en la matriz de entrada.