list - 调用降序排序或仅对列表进行排序并反转它更好吗？

Question

List模块包含sortDescending将列表从高到低排序的函数。我读到，对列表进行排序然后反转它会更快。于是我尝试了一下，似乎是这样的。

 [1.0..1000000.0] |> List.sortDescending;;
Real: 00:00:00.322, CPU: 00:00:00.328, GC gen0: 10, gen1: 4, gen2: 0

[1.0..1000000.0] |> List.sort |> List.rev;;
Real: 00:00:00.243, CPU: 00:00:00.250, GC gen0: 15, gen1: 7, gen2: 0

(我尝试了很多次，这些值都是典型值)

有什么理由使用sortDescending而不是仅仅对列表进行排序然后反转结果？

Answer 1

目前，只有对于没有标识的事物(例如整数和 float )，排序和反转才应该更快。如果你查看 github 上的源代码(请参阅 list.fs 和 local.fs)，两者都将列表复制到数组中，对数组进行排序，然后重新创建列表。

当您使用sortDescending时，它会使用stableSortInPlaceWith对数组进行排序，它始终使用stableSortWithKeysAndComparer。此功能在排序后复制结果并调整重复项目，使它们保持原始顺序。这是stable sort因此重复的项目不会移动。

排序使用stableSortInPlace，它有一个优化来检测诸如没有标识的 float 之类的东西，因此不需要使用稳定排序；没有第二个副本，使其速度更快。如果它是一个对象列表，List.sort 则使用 stableSortWithKeysAndComparer，因此它的速度应该与 List.sortDescending 相同，但由于相反的原因，速度会更慢。对于我的测试来说，速度较慢，但​​很难确定，因为我的虚拟机位于共享基础设施上，并且给出了截然不同的结果。

 [1.0..1000000.0] |> List.map Some |> List.sortDescending;;
Real: 00:00:13.616, CPU: 00:00:13.275, GC gen0: 146, gen1: 12, gen2: 5

 [1.0..1000000.0] |> List.map Some |> List.sort |> List.rev;;
Real: 00:00:17.727, CPU: 00:00:17.316, GC gen0: 149, gen1: 15, gen2: 6

正如评论中所指出的，列表已经排序，使得 List.sort 速度更快(最后我看到，.NET 对数组使用了快速排序，如果已经排序，则速度很快) 。但是，即使您首先反转列表，当它是 double 列表时，List.sort |> List.rev 仍然比 List.sortDescending 更快。​​

还要注意的是，这两者实际上并非在所有情况下都是等效的。由于它是稳定排序，因此 List.sortDescending 之后的重复项将按相同顺序排列，但它们将被 List.sort |> List.rev 反转。