并行sortingalgorithm
我正在寻找一个在C＃中的并行（multithreading）sortingalgorithm的简单实现，它可以在List<T>或Arrays上运行，并可能使用并行扩展，但这部分并不是必须的。
编辑：弗兰克克鲁格提供了一个很好的答案，但是我希望将该示例转换为一个不使用LINQ。 另请注意， Parallel.Do()似乎已被Parallel.Invoke()取代。
谢谢。
从“The Darkside”的文章“ Parallel Extensions”到.Net Framework，我们有这个并行扩展版本的quicksort：
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，他将恢复为顺序sorting。
更新我现在实现比双核心机器1.7倍的加速。
我想我会尝试编写一个在.NET 2.0中工作的并行分拣机（我想，请查看这个），并且不使用ThreadPool以外的其他任何东西。
下面是sorting一个2,000,000元素数组的结果：
时间并行时间序列 ------------- --------------- 2854毫秒5052毫秒 2846毫秒4947毫秒 2794毫秒4940毫秒 ...... 2815毫秒4894毫秒 2981 ms 4991 ms 2832毫秒5053毫秒 平均：2818毫秒平均：4969毫秒 标准：66毫秒标准：65毫秒 Spd：1.76x
我得到了1.76倍的加速 – 非常接近我希望的最佳2倍 – 在这种环境下：
- 2,000,000个随机
Model对象 - 通过比较两个
DateTime属性的比较委托sorting对象。 - 单声道JIT编译器版本2.4.2.3
- 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 ();
（其实，在代码中，我做了一点负载平衡，似乎有帮助。）
我发现运行这个并行版本只能在数组超过25000个的时候才能得到回报（尽pipe最less有5万个似乎让我的处理器更能吸引人）。
我在我的小型双核心机器上做了许多改进。 我很想尝试8路怪物的一些想法。 另外，这项工作是在一台运行Mono的13“MacBook上完成的，我很好奇其他人如何在正常的.NET 2.0上安装。
所有丑陋荣耀的源代码都可以在这里find： http : //www.praeclarum.org/so/psort.cs.txt 。 如果有兴趣，我可以把它清理干净。
这里logging的是没有lamdaexpression式的版本，它将在C＃2和.Net 2 + Parallel Extensions中编译。 这也应该与Mono自己的并行扩展实现（从谷歌暑期的代码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 }
基于处理器高速caching大小的合并sorting，其中在处理器之间划分块。
合并阶段可以通过将合并分成n位来完成，每个处理器开始将块从正确的偏移量合并到块中。
我没有试过写这个。
（由于CPUcaching和主内存的相对速度与内存和磁带的相对速度相差不远，因此我们可能应该再次开始使用合并sorting）
将需要分类的列表划分为相同大小的子列表，具体取决于您拥有多less个处理器，然后每当完成两个部分时，将它们合并到一个新的部分，直到剩下一个并完成所有线程。 非常简单，你应该可以自己实现它，并且可以使用任何现有的sortingalgorithm（如在库中）对每个线程中的列表进行sorting。
