`ImmutableSortedSet`和fsharp`Set`有什麼區別？

Question

BCL has introduced a group of Immutable Collections

我想知道什麼是ImmutableSortedSet和本地FSharp Set之間的區別？看起來兩者的表現特徵都是相似的。另外我看到SortedSet被實現爲紅黑樹，所以我猜ImmutableSortedSet也是這樣。

fsharp map的內部實現是什麼？是這裏要求的Red Black Tree還是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 map的內部實現是什麼？這裏所說的是紅黑樹還是AVL樹？

由於這兩個鏈接狀態，F＃使用AVL樹。

這實際上與上述表現數字的上下文有關。 AVL樹包含每個分支中子樹的最大高度，因此，允許在不檢查整個子樹的情況下重新平衡子樹。相比之下，紅黑樹在每個分支中包含一個數據位，因此重新平衡子樹需要遍歷整個樹，這是漸近較慢的。用外行人的話來說，兩個相同大小的非重疊集的結合只不過是創建一個包含兩棵現有樹的新分支。請注意，BCL API中的Union甚至無法表達：它處理摘要IEnumerable而不是具體集合。

此外，爲什麼MSDN文檔沒有說明庫集合的實際數據結構是什麼？我知道這些是實施細節，即將改變。我的觀點是，如果他們不想將庫數據類型綁定到特定類型的衆所周知的數據結構上，他們至少應該提供所有方法性能簽名的複雜性總結​​？

我同意文檔中的複雜性會很好。

Answer 2

F＃Set和Map類型是用AVL樹實現的。

我不知道MSDN文檔，你要問F＃團隊有關:)

在任何情況下，紅黑樹和AVL樹有其主相同的計算複雜性操作。在實踐中，它們具有不同的性能特徵，這可能導致您爲特定的應用程序選擇其中一個或另一個 - 紅黑樹的插入/刪除速度更快，因爲它們不需要對樹進行儘可能多的重新平衡，在AVL樹中更快，這要歸功於插入/刪除所執行的額外平衡。我想這就是爲什麼AVL樹被選爲F＃Map和Set實現的原因 - 一個Map/Set通常會被創建一次（即沒有被修改），然後被重複查詢。

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

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