为什么我的 Haskell 选择排序实现非常快？

Question

我实现了选择排序并将其与 Data.List 的排序进行了比较。它比 Data.List 的排序快几个数量级。如果我将其应用于 10,000 个随机生成的数字，结果如下：

 ? in 1.22µs: Selection sort
 ? in 9.84ms: Merge sort (Data.List)

这不可能是对的。首先，我认为合并排序的中间结果可能会被缓存，而选择排序使用这些结果会更快。即使我注释掉合并排序和仅时间选择排序，它也是如此之快。我还验证了输出并正确排序。

是什么导致了这种行为？

我使用此代码进行测试：

 ? in 1.22µs: Selection sort
 ? in 9.84ms: Merge sort (Data.List)

Answer 1

你写

let !v = sorter vals

这是“严格的”，但仅限于 WHNF。因此，您只是在计算找到列表中最小元素所需的时间，而不是对整个内容进行排序所需的时间。选择排序正是从这样做开始的，因此对于这个不正确的基准测试来说它是“最佳的”，而如果您只查看第一个元素，合并排序会做更多“浪费”的工作。