c# - 这种并行排序合并是否正确实现？

Question

这个并行归并排序是否正确执行？看起来是正确的，我花了 40 秒写了一个测试，它没有失败。

它的要点是我每次都需要通过将数组分成两半来进行排序。然后我试图确保我出错了，asked a question for a sanity check (我自己的理智)。我想要一个 in place sort但在看到答案时认为这太复杂了，所以我实现了以下内容。

当然，创建任务/线程来对 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);
}

Answer 1

您可以使用任务并行库为您提供更好的线程抽象和更清晰的代码。下面的示例使用了它。

除了使用 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 上阅读关于实现的讨论。