我正在寻找 C# 中并行化（多线程）排序算法的简单实现，该算法可以对List<T>数组或数组进行操作，并且可能使用并行扩展，但这部分并不是绝对必要的。
编辑：Frank Krueger 提供了一个很好的答案，但是我希望将该示例转换为不使用 LINQ 的示例。另请注意，Parallel.Do()似乎已被Parallel.Invoke().
谢谢。
问问题
25351 次
5 回答
46
从他的文章Parallel Extensions to the .Net Framework中的“The Darkside”，我们有这个快速排序的并行扩展版本：
（编辑：由于链接现已失效，感兴趣的读者可以在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，他就会恢复为顺序排序。
于 2009-12-13T19:36:48.807 回答
8
更新我现在在双核机器上实现了超过 1.7 倍的加速。
我想我会尝试编写一个在 .NET 2.0 中工作的并行排序器（我想，请检查我）并且除了ThreadPool.
以下是对 2,000,000 个元素的数组进行排序的结果：
时间并行时间序列 ------------- --------------- 2854 毫秒 5052 毫秒 2846 毫秒 4947 毫秒 2794 毫秒 4940 毫秒 …… 2815 毫秒 4894 毫秒 2981 毫秒 4991 毫秒 2832 毫秒 5053 毫秒 平均：2818 毫秒 平均：4969 毫秒 标准：66 毫秒标准：65 毫秒 速度：1.76x
在这种环境下，我得到了 1.76 倍的加速——非常接近我希望的最佳 2 倍：
- 2,000,000 个随机
Model对象 DateTime通过比较两个属性的比较委托对对象进行排序。- Mono 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 ();
（实际上，在代码中我做了一些负载平衡，似乎确实有帮助。）
我发现运行这个并行版本只有在数组中有超过 25,000 个项目时才会得到回报（不过，至少 50,000 个似乎让我的处理器喘不过气来）。
我已经在我的小型双核机器上进行了尽可能多的改进。我很想尝试一些关于 8 路怪物的想法。此外，这项工作是在一台运行 Mono 的 13 英寸 MacBook 上完成的。我很好奇其他人在正常的 .NET 2.0 安装上的表现如何。
可在此处获得所有丑陋荣耀的源代码：http: //www.praeclarum.org/so/psort.cs.txt。如果有兴趣我可以清理它。
于 2009-12-13T23:31:22.967 回答
7
作为记录，这里是一个没有 lamda 表达式的版本，它将在 C#2 和 .Net 2 + Parallel Extensions 中编译。这也应该与 Mono 一起使用它自己的并行扩展实现（来自 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
}
于 2009-12-13T22:33:42.997 回答
6
想到基于处理器缓存大小的合并排序，并在处理器之间划分块。
合并阶段可以通过将合并拆分为 n 位来完成，每个处理器开始将块从正确的偏移量合并到块中。
我没有试过写这个。
（由于 CPU 缓存和主内存的相对速度，与发现合并排序时 RAM 和磁带的相对速度相差不远，也许我们应该重新开始使用合并排序）
于 2010-02-23T15:32:13.303 回答
1
根据您拥有的处理器数量，将您需要排序的列表划分为大小相等的子列表，然后每当完成两个部分时，将它们合并到一个新部分，直到只剩下一个并且所有线程都完成。非常简单，您应该能够自己实现它，并且可以使用任何现有的排序算法（例如在库中）对每个线程中的列表进行排序。
于 2009-12-13T19:37:18.757 回答