我已经在C#中实现了快速排序的一个版本,并进行了一些快速基准测试,以与C# List<T>.Sort
进行比较。我发现我的实现比库版本慢得多。我正在尝试理解为什么会这样。以下是一些粗略的基准测试数字。对于输入,我使用了随机生成的整数列表(均匀分布)和少量重复元素。请注意,所有基准测试时间都是若干次运行的平均值。
100,000 elements
My code 0.096 seconds
List<T>.Sort 0.011 seconds
1,000,000 elements
My code 1.10 seconds
List<T>.Sort 0.14 seconds
我的代码如下。这是我尝试过的优化措施及其结果列表:
- 内联 - 我试图内联我的
Swap
和ChoosePivotIndex
函数,使用时有约 10% 的提升。 - 枢轴选择 - 我知道我使用了一个天真的枢轴选择方法。我尝试过选用三个随机元素的中位数来作为枢轴,但没有多大改进。我猜测这是因为我用于基准测试的输入数据是均匀随机的。
- 并行处理 - 我尝试使递归的 Partition 调用并行处理。这似乎实际上增加了执行时间。
- 特殊情况小输入 - 我尝试切换到插入排序来处理小输入(就像
List<T>.Sort
所声称的那样)。这可以使性能提高约 20%。
通过这些优化措施的组合,我已经将代码压缩到了...
100,000 elements - 0.062 seconds
1,000,000 elements - 0.740 seconds
这仍然比库排序慢得多。我的代码中是否有任何明显的问题可以解释性能差距,还是剩下的70-80%差距来自更小的调整?请注意,下面的代码是我的基本未优化版本
public class Quicksorter<T> where T : IComparable<T>
{
protected Random random;
public Quicksorter()
{
random = new Random();
}
public void Sort(IList<T> items)
{
Partition(items, 0, items.Count-1);
}
private void Partition(IList<T> items, int startIndex, int endIndex)
{
if (startIndex >= endIndex)
return;
int pivotIndex = ChoosePivotIndex(items, startIndex, endIndex);
T pivot = items[pivotIndex];
// swap pivot and first element
Swap(items, startIndex, pivotIndex);
int partitionIndex = startIndex + 1;
for (int frontierIndex = partitionIndex; frontierIndex <= endIndex; frontierIndex++)
{
if (items[frontierIndex].CompareTo(pivot) < 0)
{
Swap(items, frontierIndex, partitionIndex);
partitionIndex++;
}
}
// put pivot back
items[startIndex] = items[partitionIndex-1];
items[partitionIndex - 1] = pivot;
// recursively sort left half
Partition(items, startIndex, partitionIndex - 2);
// recursively sort right half
Partition(items, partitionIndex, endIndex);
}
protected virtual int ChoosePivotIndex(IList<T> items, int startIndex, int endIndex)
{
return random.Next(startIndex, endIndex);
}
private void Swap(IList<T> items, int aIndex, int bIndex)
{
T temp = items[aIndex];
items[aIndex] = items[bIndex];
items[bIndex] = temp;
}
}
List<T>
是使用数组实现的。当您调用List.Sort
时,它会转而调用Array.Sort
。在排序时间方面,数组和列表之间没有区别(除了一个额外的函数调用)。将Partition
修改为接受一个数组最终会要求 Quicksort 方法从传递的IList
创建一个数组——以 O(n) 的额外空间代价——并且在排序完成后还需要将其复制回IList
。这可能非常昂贵。 - Jim Mischel