sorting - 为什么F#'s Seq.sortBy much slower than LINQ'的IEnumerable <T> .OrderBy扩展方法？

我最近编写了一段代码，以从文件中读取一些数据，将其存储在元组中，并按元组的第一个元素对所有收集的数据进行排序。经过一些测试后，我注意到使用Seq.sortBy(和Array.sortBy)比使用IEnumerable.OrderBy极其慢。
以下是两个代码段，应显示我在谈论的行为:

(filename
|> File.ReadAllLines
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries)
                                |> Array.map(double)
                                |> Array.sort in arr.[0], arr.[1])
).OrderBy(new Func(fun (a,b) -> a))

和

filename
|> File.ReadAllLines
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) |> Array.map(double) |> Array.sort in arr.[0], arr.[1])
|> Seq.sortBy(fun (a,_) -> a)

在一个包含100000行(由两个 double 组成)的文件中，在我的计算机上，后一个版本的接收时间是第一个双倍的两倍(如果使用Array.sortBy，则无法获得任何改进)。
有想法吗？

最佳答案

f＃实现使用结果键的结构比较。

let sortBy keyf seq =
    let comparer = ComparisonIdentity.Structural
    mkDelayedSeq (fun () ->
        (seq
        |> to_list
        |> List.sortWith (fun x y -> comparer.Compare(keyf x,keyf y))
        |> to_array) :> seq<_>)

(也排序)

let sort seq =
    mkDelayedSeq (fun () ->
        (seq
        |> to_list
        |> List.sortWith Operators.compare
        |> to_array) :> seq<_>)

最终，Operators.compare和CompareIdentity.Structural.Compare都变为

let inline GenericComparisonFast<'T> (x:'T) (y:'T) : int =
    GenericComparisonIntrinsic x y
        // lots of other types elided
        when 'T : float = if (# "clt" x y : bool #)
                          then (-1)
                          else (# "cgt" x y : int #)

但是针对Operator的路由完全是内联的，因此JIT编译器最终将插入一条直接的双重比较指令，除了(无论如何，在两种情况下都需要)委托(delegate)调用之外，没有其他方法调用开销。

sortBy使用比较器，因此将通过附加的虚拟方法调用，但基本上是相同的。

相比之下，OrderBy函数还必须通过虚拟方法来调用相等性(使用EqualityComparer<T>.Default)，但是最大的区别是它排序到位并使用为此创建的缓冲区。相比之下，如果您查看sortBy，您会发现它对列表进行了排序(不在适当的位置，它使用了看起来像是合并排序的StableSortImplementation)，然后创建了它的副本作为新数组。尽管不同的排序实现也可能会产生影响，但此附加副本(根据输入数据的大小)可能是导致速度降低的主要原因。

那就是所有这些猜测。如果从性能方面来说，这是您所关心的问题，那么您只需要配置文件即可找出花费时间。

如果您希望查看排序/复制更改的效果，请尝试以下替代方法:

// these are taken from the f# source so as to be consistent
// beware doing this, the compiler may know about such methods
open System.Collections.Generic
let mkSeq f =
    { new IEnumerable<'b> with
        member x.GetEnumerator() = f()
      interface System.Collections.IEnumerable with
        member x.GetEnumerator() = (f() :> System.Collections.IEnumerator) }

let mkDelayedSeq (f: unit -> IEnumerable<'T>) =
    mkSeq (fun () -> f().GetEnumerator())

// the function
let sortByFaster keyf seq =
    let comparer = ComparisonIdentity.Structural
    mkDelayedSeq (fun () ->
        let buffer = Seq.to_array seq
        Array.sortInPlaceBy (fun x y -> comparer.Compare(keyf x,keyf y)) buffer
        buffer :> seq<_>)

我在具有很大(>百万个)输入序列的repl中得到了一些合理的加速百分比，但是却没有一个数量级。与往常一样，您的里程可能会有所不同。

关于sorting - 为什么F#'s Seq.sortBy much slower than LINQ'的IEnumerable <T> .OrderBy扩展方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1073227/