代码之家 › 专栏 › 技术社区 › em70

为什么f的seq.sortby比linq的ienumerable<t>orderby扩展方法慢得多?

inline f# sorting

em70 · 技术社区 · 15 年前

我最近编写了一段代码,用于从文件中读取一些数据,将其存储在一个元组中,并按该元组的第一个元素对收集到的所有数据进行排序。在一些测试之后,我注意到使用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,则不会得到任何改进)。思想?

2 回复 | 直到 8 年前

ShuggyCoUk 15 年前

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<_>)

两个operator.compare和comparisonIdentity.structure.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 #)

但是对于运算符来说,这条路径完全是内联的,因此JIT编译器最终将插入一条直接的双比较指令,除了委托调用(在这两种情况下都是必需的)之外,没有额外的方法调用开销。

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中得到了一些合理的百分比加速,输入序列非常大(>百万),但没有什么比数量级更重要的了。你的里程,一如既往,可能会有所不同。

Richard 15 年前

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

数据结构上的微小差异(例如优化输入 ICollection<T> )可能会造成这种差异。

而f目前是beta版本(没有太多的关注优化与正确的语言和库),加上f函数的一般性(支持部分应用程序等)可能导致调用速度略有放缓:这足以解释不同之处。