`ImmutableSortedSet`和fsharp`Set`有什么区别？

Question

BCL推出了一组不可变集合

我想知道ImmutableSortedSet和原生FSharp有Set什么区别？似乎两者的性能签名是相似的.我也看到SortedSet了一个实现为红黑树的地方,所以我猜ImmutableSortedSet也是如此.

fsharp的内部实现是什么map？这里声称是红黑树还是AVL树在这里找到了？

另外,为什么MSDN文档没有说清楚库集合的实际数据结构是什么？我知道这些是实施细节,即将改变.我的观点是,如果他们不想将库数据类型绑定到某种类型的众所周知的数据结构,他们至少应该在复杂性方面提供所有方法性能签名的总结？

Answer 1

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

Answer 2

我想知道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地图的内部实现是什么？这里声称是红黑树还是AVL树在这里找到了？

由于两个链接都是状态,F#使用AVL树.

这实际上与上述绩效数据相关.AVL树包含每个分支中子树的最大高度,因此允许在不检查整个子树的情况下重新平衡子树.相比之下,红黑树在每个分支中包含一位数据,因此重新平衡子树需要遍历整个树,这些树渐近地变慢.通俗地说,两个相同大小的非重叠集的并集只需要创建一个包含两个现有树的新分支.请注意,UnionBCL API中甚至无法表达这一点:它处理抽象IEnumerable而不是具体集.

另外,为什么MSDN文档没有说清楚库集合的实际数据结构是什么？我知道这些是实施细节,即将改变.我的观点是,如果他们不想将库数据类型绑定到某种类型的众所周知的数据结构,他们至少应该在复杂性方面提供所有方法性能签名的总结？

我同意文档中的复杂性会很好.