5

最近、ファイルからデータを読み取り、それをタプルに格納し、収集されたすべてのデータをタプルの最初の要素で並べ替えるコードを作成しました。いくつかのテストの後、Seq.sortBy（およびArray.sortBy）の使用はIEnumerable.OrderByの使用よりも非常に遅いことに気付きました。以下は、私が話している動作を示すはずの2つのコードスニペットです。


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

2つのdoubleで構成される100000行を含むファイルでは、私のコンピューターでは、後者のバージョンは最初のバージョンの2倍の時間がかかります（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＃は現在ベータ版です（言語とライブラリを正しく取得することと最適化にあまり重点を置いていません）。さらに、F＃関数の一般性（部分適用などのサポート）により、呼び出し速度がわずかに遅くなる可能性があります。異なることを説明します。

于 2009-07-02T09:22:24.633 に答える