`ImmutableSortedSet`とfsharp` Set`の違いは何ですか？

Question

BCL has introduced a group of Immutable Collections

私はImmutableSortedSetとネイティブFSharp Setの違いは何でしょう疑問に思って？両方のパフォーマンス・シグネチャは似ているようです。また、SortedSetがRed Black Treeとして実装されていることがわかりましたので、ImmutableSortedSetは同じことをしています。

fsharp mapの内部実装とは何ですか？ここに記載されているまたはAVL treeはここにありますか？

さらに、MSDNドキュメントで実際のデータ構造がライブラリコレクションの内容を明確にしていないのはなぜですか？私はこれらが実装の詳細であり、変更しようとしていることを知っています。私のポイントは、ライブラリーのデータ型を特定のタイプのよく知られているデータ構造にバインドしたくない場合は、少なくとも複雑さの点ですべてのメソッドのパフォーマンスの署名を提供する必要があります。

Answer 1

私はImmutableSortedSetとネイティブFSharp設定の違い何疑問に思って？

これらは一般に非常によく似ています。主な相違点は、F＃Setが高速集合理論演算（和集合、交差点および相違点）をサポートしていることです。ここで

は、いくつかの一般的な操作のパフォーマンスを測定し、単純なF＃のプログラムである：私のマシン上で

open System.Collections.Immutable 

while true do 
    do 
    let timer = System.Diagnostics.Stopwatch.StartNew() 
    let cmp = LanguagePrimitives.FastGenericComparer<int> 
    let mutable s1 = ImmutableSortedSet.Create<int>(cmp) 
    let mutable s2 = ImmutableSortedSet.Create<int>(cmp) 
    for i in 1..1000000 do 
     s1 <- s1.Add i 
    for i in 1000000..2000000 do 
     s2 <- s2.Add i 
    printfn "BCL ImmutableSortedSet: add in %fs" timer.Elapsed.TotalSeconds 
    timer.Restart() 
    for _ in 1..10 do 
     for i in 1..1000000 do 
     ignore(s1.Contains i) 
    printfn "BCL ImmutableSortedSet: contains in %fs" timer.Elapsed.TotalSeconds 
    timer.Restart() 
    let s = s1.Union s2 
    printfn "BCL ImmutableSortedSet: union in %fs" timer.Elapsed.TotalSeconds 

    do 
    let timer = System.Diagnostics.Stopwatch.StartNew() 
    let mutable s1 = Set.empty 
    let mutable s2 = Set.empty 
    for i in 1..1000000 do 
     s1 <- s1.Add i 
    for i in 1000000..2000000 do 
     s2 <- s2.Add i 
    printfn "F# Set: %fs" timer.Elapsed.TotalSeconds 
    timer.Restart() 
    for _ in 1..10 do 
     for i in 1..1000000 do 
     ignore(s1.Contains i) 
    printfn "F# Set: contains in %fs" timer.Elapsed.TotalSeconds 
    timer.Restart() 
    let s = Set.union s1 s2 
    printfn "F# Set: union in %fs" timer.Elapsed.TotalSeconds 

を、私が手：

  BCL ImmutableSortedSet F# Set 
add    2.6s   3.0s 
contains   2.1s   1.9s 
union    1.1s   0.00004s 

だから、F＃のSetが構築する少し遅く、検索の速度はやや速くなりますが、設定された理論的な結合演算ではより速くなります。

fsharpマップの内部実装とは何ですか？ Red Black TreeはここにあるとAVLツリーが主張しているのですか？

両方のリンクが状態であるため、F＃はAVLツリーを使用します。

これは実際に上記のパフォーマンス数値の文脈では適切です。 AVLツリーには、各ブランチ内のサブツリーの最大高さが含まれているため、サブツリー全体を調べなくてもサブツリーの再調整が可能です。対照的に、赤黒の木は各枝に1ビットのデータを含んでいるので、部分木を再平衡させるためには樹木全体が漸進的にゆっくり移動する必要があります。素人の言葉では、2つの同じ大きさの重なり合わない集合の和集合は、2つの既存の木を含む新しい枝を作成することに過ぎない。 BCL APIのUnionはこれを表現することさえできません。具体的なセットではなく、抽象的なIEnumerableを処理します。

さらに、MSDNドキュメントで実際のデータ構造がライブラリコレクションにどのようなものであるかが明確になっていないのはなぜですか？私はこれらが実装の詳細であり、変更しようとしていることを知っています。私のポイントは、ライブラリーのデータ型を特定のタイプのよく知られているデータ構造にバインドしたくない場合は、少なくとも複雑さの点ですべてのメソッドのパフォーマンスの署名を提供する必要があります。

私は、ドキュメントの複雑さが良いと同意します。

Answer 2

F＃セットとマップタイプは、AVLツリーで実装されています。

私は、MSDNのドキュメントについて知らない、あなたはそれについてのF＃チームに依頼する:)

いずれの場合もあるんだけど、赤黒の木とAVL木は彼らのメインのため、同じ計算の複雑さを持っていますオペレーション。実際には、それらは異なるパフォーマンス特性を持ち、特定のアプリケーションに合わせてどちらか一方を選択する可能性があります。Red-Blackツリーは、ツリーのリバランスをあまり必要としないため、挿入/削除が高速ですが、挿入/削除のための追加のバランシングにより、AVLツリーの方が高速です。私はそれがF＃MapとSetの実装のためにAVLツリーが選ばれた理由だと思っています。マップ/セットは、通常、一度作成（すなわち変更されない）され、次に繰り返し照会されます。

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

https://en.wikipedia.org/wiki/AVL_tree