señal - metodos de ordenamiento c#

Algoritmo de ordenamiento paralelo

Question

Estoy buscando una implementación simple de un algoritmo de ordenamiento en paralelo (de múltiples subprocesos) en C # que pueda operar en List<T> o Arrays, y posiblemente utilizando extensiones paralelas, pero esa parte no es estrictamente necesaria.

Editar: Frank Krueger proporciona una buena respuesta, sin embargo, deseo convertir ese ejemplo a uno que no use LINQ. También tenga en cuenta que Parallel.Do() parece haber sido reemplazado por Parallel.Invoke() .

Gracias.

Answer 1

Desde "The Darkside" en su artículo Parallel Extensions para .Net Framework tenemos esta versión de extensiones paralelas de quicksort:

(Editar: dado que el enlace está ahora muerto, los lectores interesados ​​pueden encontrar un archivo del mismo en Wayback Machine )

private void QuicksortSequential<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    if (right > left)
    {
        int pivot = Partition(arr, left, right);
        QuicksortSequential(arr, left, pivot - 1);
        QuicksortSequential(arr, pivot + 1, right);
    }
}

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    const int SEQUENTIAL_THRESHOLD = 2048;
    if (right > left)
    {
        if (right - left < SEQUENTIAL_THRESHOLD)
        {

            QuicksortSequential(arr, left, right);
        }
        else
        {
            int pivot = Partition(arr, left, right);
            Parallel.Do(
                () => QuicksortParallelOptimised(arr, left, pivot - 1),
                () => QuicksortParallelOptimised(arr, pivot + 1, right));
        }
    }
}

Tenga en cuenta que vuelve a un tipo secuencial una vez que la cantidad de elementos es inferior a 2048.

Answer 2

Divida la lista que necesita ordenada en sublistas de igual tamaño, según la cantidad de procesadores que tenga, y cada vez que haya dos partes juntas, agréguelos a una nueva parte, hasta que quede solo una y todos los hilos terminados. Muy simple, debería poder implementarlo usted mismo, y ordenar las listas dentro de cada hilo se puede hacer usando cualquier algoritmo de ordenamiento existente (como en la biblioteca).

Answer 3

Me viene a la mente un tipo de fusión basado en el tamaño del caché del procesador, con los bloques divididos entre los procesadores.

La etapa de fusión podría hacerse dividiendo la combinación en n bits con cada procesador comenzando a fusionar los bloques del desplazamiento correcto en los bloques.

No he intentado escribir esto.

(Debido a que la velocidad relativa de la memoria caché de la CPU y del ram principal no está tan lejos de la velocidad relativa de la RAM y la cinta como el momento en que se descubrió el tipo de fusión, tal vez deberíamos empezar a utilizar ordenaciones de fusión nuevamente)

Answer 4

Para el registro aquí hay una versión sin expresiones lamda que se compilará en C # 2 y .Net 2 + Parallel Extensions. Esto también debería funcionar con Mono con su propia implementación de Extensiones Paralelas (de Google Summer del código 2008):

/// <summary>
/// Parallel quicksort algorithm.
/// </summary>
public class ParallelSort
{
    #region Public Static Methods

    /// <summary>
    /// Sequential quicksort.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr"></param>
    public static void QuicksortSequential<T>(T [] arr) where T : IComparable<T>
    {
        QuicksortSequential(arr, 0, arr.Length - 1);
    }

    /// <summary>
    /// Parallel quicksort
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr"></param>
    public static void QuicksortParallel<T>(T[] arr) where T : IComparable<T>
    {
        QuicksortParallel(arr, 0, arr.Length - 1);
    }

    #endregion

    #region Private Static Methods

    private static void QuicksortSequential<T>(T[] arr, int left, int right) 
        where T : IComparable<T>
    {
        if (right > left)
        {
            int pivot = Partition(arr, left, right);
            QuicksortSequential(arr, left, pivot - 1);
            QuicksortSequential(arr, pivot + 1, right);
        }
    }

    private static void QuicksortParallel<T>(T[] arr, int left, int right) 
        where T : IComparable<T>
    {
        const int SEQUENTIAL_THRESHOLD = 2048;
        if (right > left)
        {
            if (right - left < SEQUENTIAL_THRESHOLD)
            {
                QuicksortSequential(arr, left, right);
            }
            else
            {
                int pivot = Partition(arr, left, right);
                Parallel.Invoke(new Action[] { delegate {QuicksortParallel(arr, left, pivot - 1);},
                                               delegate {QuicksortParallel(arr, pivot + 1, right);}
                });
            }
        }
    }

    private static void Swap<T>(T[] arr, int i, int j)
    {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int Partition<T>(T[] arr, int low, int high) 
        where T : IComparable<T>
    {
        // Simple partitioning implementation
        int pivotPos = (high + low) / 2;
        T pivot = arr[pivotPos];
        Swap(arr, low, pivotPos);

        int left = low;
        for (int i = low + 1; i <= high; i++)
        {
            if (arr[i].CompareTo(pivot) < 0)
            {
                left++;
                Swap(arr, i, left);
            }
        }

        Swap(arr, low, left);
        return left;
    }

    #endregion
}

Answer 5

Actualización Ahora logro una velocidad superior a 1.7x en una máquina de doble núcleo.

Pensé que trataría de escribir un clasificador paralelo que funcionara en .NET 2.0 (creo, revisen esto) y que no use nada más que ThreadPool .

Estos son los resultados de ordenar una matriz de 2,000,000 de elementos:

Time Parallel Time Sequential ------------- --------------- 2854 ms 5052 ms 2846 ms 4947 ms 2794 ms 4940 ms ... ... 2815 ms 4894 ms 2981 ms 4991 ms 2832 ms 5053 ms Avg: 2818 ms Avg: 4969 ms Std: 66 ms Std: 65 ms Spd: 1.76x

Obtuve una aceleración de 1.76x, bastante cerca del óptimo 2x que esperaba, en este entorno:

1. 2,000,000 objetos Model azar
2. Clasificación de objetos por un delegado de comparación que compara dos propiedades de DateTime .
3. Compilador Mono JIT versión 2.4.2.3
4. Max OS X 10.5.8 en Intel Core 2 Duo de 2.4 GHz

Esta vez utilicé QuickSort de Ben Watson en C # . Cambié su lazo interno QuickSort de:

QuickSortSequential:
    QuickSortSequential (beg, l - 1);
    QuickSortSequential (l + 1, end);

a:

QuickSortParallel:
    ManualResetEvent fin2 = new ManualResetEvent (false);
    ThreadPool.QueueUserWorkItem (delegate {
        QuickSortParallel (l + 1, end);
        fin2.Set ();
    });
    QuickSortParallel (beg, l - 1);
    fin2.WaitOne (1000000);
    fin2.Close ();

(En realidad, en el código hago un poco de equilibrio de carga que parece ayudar.)

Descubrí que ejecutar esta versión en paralelo solo vale la pena cuando hay más de 25,000 elementos en una matriz (aunque un mínimo de 50,000 parece permitir que mi procesador respire más).

He hecho tantas mejoras como puedo pensar en mi pequeña máquina de doble núcleo. Me encantaría probar algunas ideas sobre el monstruo de 8 vías. Además, este trabajo se realizó en una pequeña MacBook de 13 "que ejecutaba Mono. Tengo curiosidad sobre cómo les va a otros en una instalación .NET 2.0 normal.

El código fuente en toda su fea gloria está disponible aquí: http://www.praeclarum.org/so/psort.cs.txt . Puedo limpiarlo si hay algún interés.