C# 并行排序算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1897458/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Parallel Sort Algorithm
提问by redcalx
I'm looking for a simple implementation of a parallelized (multi-threaded) sort algorithm in C# that can operate on List<T>or Arrays, and possibly using Parallel Extensions but that part isn't strictly necessary.
我正在寻找 C# 中并行化（多线程）排序算法的简单实现，它可以对List<T>数组或数组进行操作，并且可能使用并行扩展，但这部分并不是绝对必要的。
Edit: Frank Krueger provides a good answer, however I wish to convert that example to one that doesn't use LINQ. Also note that Parallel.Do()seems to have been superceded by Parallel.Invoke().
编辑：Frank Krueger 提供了一个很好的答案，但是我希望将该示例转换为不使用 LINQ 的示例。另请注意，Parallel.Do()似乎已被Parallel.Invoke().
Thanks.
谢谢。
采纳答案by Frank Krueger
From "The Darkside" in his article Parallel Extensions to the .Net Frameworkwe have this parallel extensions version of quicksort:
从他的文章Parallel Extensions to the .Net Framework 中的“The Darkside”中，我们得到了快速排序的并行扩展版本：
(Edit: Since the link is now dead, interested readers may find an archive of it at the Wayback Machine)
（编辑：由于链接现已失效，感兴趣的读者可以在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));
}
}
}
Notice that he reverts to a sequential sort once the number of items is less than 2048.
请注意，一旦项目数小于 2048，他就会恢复到顺序排序。
回答by KernelJ
Divide the list you need sorted into equal sized sublists, depending on how many processors you have, and then whenever two parts are done, merge them together to a new part, until there is only one left and all threads completed. Very simple you should be able to implement it yourself, and sorting the lists within each thread can be done using any existing sort algorithm (like in the library).
将您需要的列表分成大小相等的子列表，具体取决于您拥有的处理器数量，然后每当完成两个部分时，将它们合并为一个新部分，直到只剩下一个并且所有线程都完成为止。非常简单，您应该能够自己实现它，并且可以使用任何现有的排序算法（例如在库中）对每个线程中的列表进行排序。
回答by redcalx
For the record here is a version without lamda expressions that will compile in C#2 and .Net 2 + Parallel Extensions. This should also work with Mono with its own implementation of Parallel Extensions (from Google Summer of code 2008):
这里的记录是一个没有 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
}
回答by Frank Krueger
UpdateI now achieve better than 1.7x speedup on a dual core machine.
更新我现在在双核机器上实现了比 1.7 倍更好的加速。
I thought I would try writing a parallel sorter that worked in .NET 2.0 (I think, check me on this) and that doesn't use anything other than the ThreadPool.
我想我会尝试编写一个在 .NET 2.0 中工作的并行排序器（我认为，请检查我）并且除了ThreadPool.
Here are the results of sorting a 2,000,000 element array:
以下是对 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
I got a 1.76x speedup - pretty close to the optimal 2x I was hoping for - in this environment:
在这种环境中，我获得了 1.76 倍的加速 - 非常接近我希望的最佳 2 倍：
- 2,000,000 random
Modelobjects - Sorting objects by a comparison delegate that compares two
DateTimeproperties. - Mono JIT compiler version 2.4.2.3
- Max OS X 10.5.8 on 2.4 GHz Intel Core 2 Duo
- 2,000,000 个随机
Model对象 - 通过比较两个
DateTime属性的比较委托对对象进行排序。 - Mono JIT 编译器版本 2.4.2.3
- Max OS X 10.5.8 on 2.4 GHz Intel Core 2 Duo
This time I used Ben Watson's QuickSort in C#. I changed his QuickSortinner loop from:
这次我在 C# 中使用了Ben Watson 的 QuickSort。我改变了他的QuickSort内循环：
QuickSortSequential:
QuickSortSequential (beg, l - 1);
QuickSortSequential (l + 1, end);
to:
到：
QuickSortParallel:
ManualResetEvent fin2 = new ManualResetEvent (false);
ThreadPool.QueueUserWorkItem (delegate {
QuickSortParallel (l + 1, end);
fin2.Set ();
});
QuickSortParallel (beg, l - 1);
fin2.WaitOne (1000000);
fin2.Close ();
(Actually, in the code I do a little load balancing that does seem to help.)
（实际上，在代码中我做了一些似乎有帮助的负载平衡。）
I've found that running this parallel version only pays off when there are more than 25,000 items in an array (though, a minimum of 50,000 seems to let my processor breath more).
我发现只有当数组中有超过 25,000 个项目时，运行这个并行版本才会有回报（尽管至少 50,000 似乎让我的处理器呼吸更多）。
I've made as many improvements as I can think of on my little dual core machine. I would love to try some ideas on 8-way monster. Also, this work was done on a little 13" MacBook running Mono. I'm curious how others fare on a normal .NET 2.0 install.
我在我的小型双核机器上进行了尽可能多的改进。我很想尝试一些关于 8 路怪物的想法。此外，这项工作是在运行 Mono 的 13" 小 MacBook 上完成的。我很好奇其他人在正常的 .NET 2.0 安装上的表现如何。
The source code in all its ugly glory is availble here: http://www.praeclarum.org/so/psort.cs.txt. I can clean it up if there's any interest.
所有丑陋荣耀的源代码都可以在这里找到：http: //www.praeclarum.org/so/psort.cs.txt。如果有兴趣，我可以清理它。
回答by Ian Ringrose
A merge sort based on the size of the processor cache, with the blocks being divided between the processors comes to mind.
一种基于处理器缓存大小的归并排序，在处理器之间划分的块浮现在脑海中。
The merge stage could be done by splitting the merge into n bits with each processor starting to merge the blocks from the correct offset into the blocks.
合并阶段可以通过将合并拆分为 n 位来完成，每个处理器开始将来自正确偏移量的块合并到块中。
I have not tried writing this.
我没试过写这个。
(As the relative speed of CPU cache and main ram, is not that far off the relative speed of RAM and Tape as the time the merge sort was discovered, maybe we should start using merge sorts again)
（由于CPU缓存和主内存的相对速度，与发现合并排序时RAM和磁带的相对速度相差不远，也许我们应该重新开始使用合并排序）
