什么'；是“ImmutableSortedSet”和fsharp“Set”之间的区别

本文关键字：Set fsharp 之间 区别 ImmutableSortedSet 什么 | 更新日期: 2023-09-27 18:10:48

BCL引入了一组不可变集合

我想知道ImmutableSortedSet和原生FSharp Set之间有什么区别？两者的性能特征似乎相似。我还在某个地方看到SortedSet被实现为红黑树，所以我想ImmutableSortedSet也做了同样的事情。

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

此外，为什么MSDN文档没有明确说明库集合的实际数据结构是什么？我知道这些都是实现细节，并且即将更改。我的观点是，如果他们不想将库数据类型绑定到某种类型的众所周知的数据结构，他们至少应该提供所有方法性能签名的复杂性摘要？

什么'；是“ImmutableSortedSet”和fsharp“Set”之间的区别

F#Set和Map类型是用AVL树实现的。

我不知道MSDN文档，你必须向F#团队询问：(

在任何情况下，红-黑树和AVL树的主要运算具有相同的计算复杂度。在实践中，它们具有不同的性能特征，这可能会导致您为特定的应用程序选择其中一种——红-黑树的插入/删除速度更快，因为它们不需要对树进行太多的重新平衡，但在AVL树中检索速度更快，这要归功于它为插入/删除执行的额外平衡。我想这就是为什么为F#Map和Set实现选择AVL树的原因——Map/Set通常创建一次(即不修改(，然后重复查询。

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

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

我想知道ImmutableSortedSet和原生FSharp Set之间有什么区别？

它们通常非常相似。主要区别在于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树包含每个分支中子树的最大高度，因此，允许在不检查整个子树的情况下重新平衡子树。相比之下，红黑树在每个分支中都包含一位数据，因此重新平衡子树需要遍历整个树，这是渐进较慢的。用外行的话来说，两个大小相同的非重叠集合的并集只需要创建一个包含两个现有树的新分支。请注意，BCL API中的Union甚至不能表达这一点：它处理抽象的IEnumerable，而不是具体的集合。

此外，为什么MSDN文档没有明确说明库集合的实际数据结构是什么？我知道这些都是实现细节，并且即将更改。我的观点是，如果他们不想将库数据类型绑定到某种类型的众所周知的数据结构，他们至少应该提供所有方法性能签名的复杂性摘要？

我同意文档中的复杂性是好的。

相关文章：