并行排序算法

Question

我正在寻找C#中的并行化(多线程)排序算法的简单实现,它可以在List<T>Arrays上运行,也可能使用Parallel Extensions,但这部分并不是绝对必要的.

编辑:Frank Krueger提供了一个很好的答案,但我希望将该示例转换为不使用LINQ的示例.还要注意,Parallel.Do()似乎已被取代了Parallel.Invoke().

谢谢.

Answer 1

从他的文章Parallel Extensions到.Net Framework的 "The Darkside",我们有quicksort的这个并行扩展版本:

(编辑:由于链接现已死亡,感兴趣的读者可能会在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));
        }
    }
}

请注意,一旦项目数小于2048,他将恢复为顺序排序.

Answer 2

更新我现在在双核机器上实现了超过1.7倍的加速.

我以为我会尝试编写一个在.NET 2.0中工作的并行分类器(我想,请检查一下),除了之外没有使用任何其他东西ThreadPool.

以下是对2,000,000个元素数组进行排序的结果:

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

我获得了1.76倍的加速 - 非常接近我希望的最佳2倍 - 在这种环境中:

1. 2,000,000随机Model对象
2. 通过比较两个DateTime属性的比较委托对对象进行排序.
3. Mono JIT编译器版本2.4.2.3
4. 2.4 GHz Intel Core 2 Duo上的Max OS X 10.5.8

这次我在C#中使用了Ben Watson的QuickSort.我改变了他的QuickSort内循环:

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

至:

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

(实际上,在代码中我做了一些看似有帮助的负载平衡.)

我发现运行这个并行版本只会在阵列中有超过25,000个项目时获得回报(但是,至少50,000个似乎让我的处理器呼吸更多).

我在我的小型双核机器上做了很多改进.我很想尝试8路怪物的一些想法.此外,这项工作是在运行Mono的13英寸MacBook上完成的.我很好奇其他人如何在正常的.NET 2.0安装上使用.

这里有丑陋荣耀的源代码:http://www.praeclarum.org/so/psort.cs.txt.如果有任何兴趣,我可以清理它.

Answer 3

这里的记录是一个没有lamda表达式的版本,它将在C#2和.Net 2 + Parallel Extensions中编译.这也应该与Mono一起使用它自己的Parallel Extensions实现(来自Google Summer of code 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 4

考虑到基于处理器高速缓存大小的合并排序,以及在处理器之间划分的块.

合并阶段可以通过将合并分成n个比特来完成,每个处理器开始将来自正确偏移的块合并到块中.

我没有尝试写这个.

(由于CPU缓存和主ram的相对速度,与发现合并排序的时间相差RAM和磁带的相对速度,可能我们应该再次开始使用合并排序)