Правильно ли реализовано это параллельное слияние? - PullRequest
Новая
       7

Правильно ли реализовано это параллельное слияние?

4 голосов
/ 13 января 2011

Правильно ли реализована параллельная сортировка слиянием?Это выглядит правильно, я потратил 40 секунд, чтобы написать тест, и он не потерпел неудачу.

Суть в том, что мне нужно отсортировать, разбивая массив пополам каждый раз.Затем я попытался убедиться, что я ошибаюсь, и задал вопрос для проверки работоспособности (мое собственное здравомыслие).Я хотел на месте сортировки , но решил, что это сложно, когда увидел ответ, поэтому я реализовал следующее.

Конечно, нет смысла создавать задачу / поток для сортировки 4байтовый массив, но его изучать многопоточность.Есть ли что-то не так или что я могу изменить, чтобы сделать это лучше.Для меня это выглядит идеально, но я хотел бы получить общий отзыв. 

static void Main(string[] args)
{
    var start = DateTime.Now;
    //for (int z = 0; z < 1000000; z++)
    int z = 0;
    while(true)
    {
        var curr = DateTime.Now;
        if (curr - start > TimeSpan.FromMinutes(1))
            break;
        var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 };
        Sort(arr, 0, arr.Length, new byte[arr.Length]);
        //Console.Write(BitConverter.ToString(arr));
        for (int i = 1; i < arr.Length; ++i)
        {
            if (arr[i] > arr[i])
            {
                System.Diagnostics.Debug.Assert(false);
                throw new Exception("Sort was incorrect " + BitConverter.ToString(arr));
            }
        }
        ++z;
    }
    Console.WriteLine("Tried {0} times with success", z);
}
static void Sort(byte[] arr, int leftPos, int rightPos, byte[] tempArr)
{
    var len = rightPos - leftPos;
    if (len < 2)
        return;
    if (len == 2)
    {
        if (arr[leftPos] > arr[leftPos + 1])
        {
            var t = arr[leftPos];
            arr[leftPos] = arr[leftPos + 1];
            arr[leftPos + 1] = t;
        }
        return;
    }
    var rStart = leftPos+len/2;
    var t1 = new Thread(delegate() { Sort(arr, leftPos, rStart, tempArr); });
    var t2 = new Thread(delegate() { Sort(arr, rStart, rightPos, tempArr); });
    t1.Start();
    t2.Start();
    t1.Join();
    t2.Join();
    var l = leftPos;
    var r = rStart;
    var z = leftPos;
    while (l<rStart && r<rightPos)
    {
        if (arr[l] < arr[r])
        {
            tempArr[z] = arr[l];
            l++;
        }
        else
        {
            tempArr[z] = arr[r];
            r++;
        }
        z++;
    }
    if (l < rStart)
        Array.Copy(arr, l, tempArr, z, rStart - l);
    else
        Array.Copy(arr, r, tempArr, z, rightPos - r);
    Array.Copy(tempArr, leftPos, arr, leftPos, rightPos - leftPos);
}

1 Ответ

6 голосов
/ 17 марта 2011

Вы можете использовать Task Parallel Library, чтобы обеспечить вам лучшую абстракцию над потоками и более чистым кодом.В приведенном ниже примере используется это.

Основное отличие от вашего кода, кроме использования TPL, заключается в том, что он имеет порог отсечения, ниже которого используется последовательная реализация независимо от количества запущенных потоков.Это предотвращает создание потоков, которые выполняют очень небольшой объем работы.Существует также ограничение глубины, ниже которого новые темы не создаются.Это предотвращает создание большего количества потоков, чем может обработать аппаратное обеспечение в зависимости от количества доступных логических ядер (Environment.ProcessCount).

Я бы порекомендовал реализовать оба этих подхода в вашем коде для предотвращения взрыва потоков для больших массивов и неэффективного создания потоков, которые выполняют очень небольшие объемы работы даже для небольших размеров массивов.Это также даст вам лучшую производительность. 

public static class Sort
{
    public static int Threshold = 150; 

    public static void InsertionSort(int[] array, int from, int to)
    {
        // ...
    }

    static void Swap(int[] array, int i, int j)
    {
        // ...
    }

    static int Partition(int[] array, int from, int to, int pivot)
    {
        // ...
    }

    public static void ParallelQuickSort(int[] array)
    {
       ParallelQuickSort(array, 0, array.Length, 
            (int) Math.Log(Environment.ProcessorCount, 2) + 4);
    }

    static void ParallelQuickSort(int[] array, int from, int to, int depthRemaining)
    {
        if (to - from <= Threshold)
        {
            InsertionSort(array, from, to);
        }
        else
        {
            int pivot = from + (to - from) / 2; // could be anything, use middle
            pivot = Partition(array, from, to, pivot);
            if (depthRemaining > 0)
            {
                Parallel.Invoke(
                    () => ParallelQuickSort(array, from, pivot, depthRemaining - 1),
                    () => ParallelQuickSort(array, pivot + 1, to, depthRemaining - 1));
            }
            else
            {
                ParallelQuickSort(array, from, pivot, 0);
                ParallelQuickSort(array, pivot + 1, to, 0);
            }
        }
    }
}

Полный исходный код доступен на http://parallelpatterns.codeplex.com/

Обсуждение реализации можно прочитать на http://msdn.microsoft.com/en-us/library/ff963551.aspx

...