4

我是并行编程的新手，我不确定为什么该QuickSortParallel方法比我的顺序版本慢（没有 Parallel.Invoke）。我有一个由十万个 9 位数字组成的锯齿状数组，我通过这些数字对其进行排序。不幸的是，当我使用该QuickSortParallel方法时，它最终比顺序版本慢了近 5 倍。

我能做的不仅仅是在数据源上使用 Parallel.Invoke 吗？ 

    public static void QuickSort_Parallel<T>(T[] array2) where T : IComparable<T>
    {
        QuickSortParallel(array2, 0, array2.Length - 1);
    }

    private static void QuickSortParallel<T>(T[] array2, int left, int right)
        where T : IComparable<T>
    {
        if (left >= right)
        {
            return;
        }

        SwapElements(array2, left, (left + right) / 2); //median pivot
        int last = left;
        for (int current = left + 1; current <= right; ++current)
        {
            //CompareTo, compares current array index value with
            if (array2[current].CompareTo(array2[left]) < 0)
            {
                ++last;
                SwapElements(array2, last, current);
            }
        }

        SwapElements(array2, left, last);
        //Recursive
        //Executes each of the provided actions in parallel.
        Parallel.Invoke(
            () => QuickSortParallel(array2, left, last - 1),
            () => QuickSortParallel(array2, last + 1, right)
        );
    }

    static void SwapElements<T>(T[] array2, int i, int j)
    {
        T temp = array2[i];
        array2[i] = array2[j];
        array2[j] = temp;
    }
4

3 回答 3

2

您的问题很可能来自线程的开销。

使用线程通常会使 CPU 密集型工作更快，但是启动一个新线程会带来大量开销，如果你给太多线程提供了太少的工作，那么你可以让你的程序运行得更慢。

当您运行以下行时：

    Parallel.Invoke(
        () => QuickSortParallel(array2, left, last - 1),
        () => QuickSortParallel(array2, last + 1, right)
    );

...您可能会导致当前线程产生另外两个线程（取决于Parallel.Invoke实现方式）。如果我的心算是正确的（如果Parallel.Invoke确实创建了新线程），那么您正在创建n * log(n)线程——一个巨大的数字！

如果你想看到性能提升，你需要平衡线程数——更多并不总是更好。使用系统线程池限制线程数的好方法：

System.Threading.ThreadPool.QueueUserWorkItem(
        () => QuickSortParallel(array2, left, last - 1));
System.Threading.ThreadPool.QueueUserWorkItem(
        () => QuickSortParallel(array2, last + 1, right));

...或类似的规定。如果您愿意，您也可以实现自己的线程池。一个

另一种选择是限制递归的深度，从而限制线程的数量。

于 2012-10-16T00:48:34.300 回答
2

所有这些递归调用都在杀死你。这篇文章http://reedcopsey.com/2010/02/26/parallelism-in-net-part-11-divide-and-conquer-via-parallel-invoke/非常相关。

于 2012-10-16T00:50:46.000 回答
0

围绕使用 SwapElements 方法的争论？尝试将 SwapElements 方法的逻辑直接放入您的方法/循环中，而不是调用它......这将使它成为每个产生的并行线程上发生的事情的一部分，而不是成为潜在的瓶颈。看看这对你有什么帮助……不过只是一个建议，不确定它是否有用。

于 2012-10-16T00:37:29.750 回答