5

我最近编写了一段代码来从文件中读取一些数据，将其存储在一个元组中，并按元组的第一个元素对所有收集的数据进行排序。经过一些测试，我注意到使用 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 行由两个双打组成的文件上，在我的计算机上，后一个版本占用的时间是第一个版本的两倍（如果使用 Array.sortBy，则不会获得任何改进）。想法？

4

2 回答 2

10

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 和 ComparisonIdentity.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 编译器最终将插入直接双重比较指令，除了（在两种情况下都需要）委托调用之外没有额外的方法调用开销。

sortBy 使用了一个比较器，因此将通过一个额外的虚拟方法调用，但基本相同。

相比之下，OrderBy 函数还必须通过虚方法调用来实现相等性（Using 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 中获得了一些合理的百分比加速，输入序列非常大（> 百万），但没有一个数量级。与往常一样，您的里程可能会有所不同。

于 2009-07-02T09:54:52.087 回答
0

当排序为 O(n.log(n)) 时，x2 的差异并不大。

数据结构的微小差异（例如优化输入ICollection<T>）可能会产生这种差异。

而且 F# 目前是 Beta 版（不太注重优化而不是让语言和库正确），加上 F# 函数的通用性（支持部分应用程序等）可能会导致调用速度略有下降：绰绰有余占不同。

于 2009-07-02T09:22:24.633 回答