c# - 快速排序正态分布的 double

Question

我们有一个对象数组。每个对象都有双重值(value)。该数组应按此值排序。数组参数为:

1. 范围是 1 - 10 000 个元素。大多数时候是 100 - 5000。 >10 000 真的不太可能
2. 值的分布接近正态
3. 值只插入一次，之后不会改变(不会对几乎已排序的数组进行重新排序)
4. 有多种这样的数据样本

现在我们使用 OrderBy 并执行如下操作:

public class Item
{
    double Value;
    //... some else data fields
}

List<Item> items;           // fill items
items.Sort(p=>p.Value);  // sort

众所周知:

1. List.Sort(与Array.Sort 相同)是一个 implementation快速排序算法。
2. Quick sort is最适合 double 的均匀分布
3. 排序的 OrderBy 实现 looks worse比 List.Sort 更适合我们的案例。

但基准测试仍然表明这种排序占用了我们 95% 的软件处理时间。

对于这种特殊情况，是否有更快的排序实现？

Answer 1

评估排序算法的问题在于，影响结果的因素有很多。我不太相信您提供的网站，因为它可能更多地对 javascript 引擎、可视化和 javascript 实现进行基准测试，而不是实际的排序算法。

Heapsort 在理论上具有良好的特性，但不能充分利用现代 CPU 优化。

QuickSort 在理论上更糟糕，但是诸如中位数 3 和中位数 9 的主元元素等常见技巧使得坏情况真的不太可能发生，并且通过线性处理数组，CPU 可以很好地优化它。

当您不需要就地排序时，MergeSort 非常有用。就地使用它并针对预排序和几乎预排序的数据对其进行优化并非易事，但您可以看看 Python 和 Java7 使用的 Tim 排序。

没有诸如“QuickSort is bad for gaussian distributed data”之类的笼统答案。理论与实践之间存在着巨大的差距。理论上，Insertion Sort 和 QuickSort 比 HeapSort 差。实际上，在大多数情况下优化良好的 QuickSort 是很难被击败的，特别是因为它很好地优化并从 CPU 缓存中获益。 Tim Sort 不是普通的归并排序。它实际上是 InsertionSort 的混合体，用于优化已排序的对象运行的常见情况。

其次，这应该是相当明显的，所提到的排序算法都没有实际计算两个对象的差异。因此，任何不产生大量重复的分布在他们看来都是一样的。他们看到的只是“小于、等于、大于”。所以分布之间的唯一区别是有多少对象是相等的!事实上，只有桶排序算法(例如基数排序)应该关心对象分布，因为它们使用超出 <=> 的实际值。比较。

对于您的特定情况，您需要检查列表的组织方式。链表真的不利于排序。事实上，如果我没记错的话，Java 会将几乎所有集合转换为 native 数组进行排序，然后重建集合。 其次，p=>p.Value的概念很漂亮，但也可能要付出相当大的代价。这可能会导致创建、管理和垃圾收集各种额外的对象。

您应该尝试的第一件事是检查是否完整的比较器比 lambda 语法概念更快。 查看内存管理。最有可能的是，这是实际工作发生的地方，复制和转换是不必要的。

例如，C# 可能会为您的数据集“double -> 索引”构建一个逆向映射，然后对该数组进行排序，然后使用该映射对您的数据进行排序。这很好，如果您的 lambda 函数非常昂贵并且应该只计算一次。