我想知道ImmutableSortedSet和native FSharp Set有什么区别？似乎两者的性能签名是相似的.另外我看到SortedSet被实现为一个红黑树的地方,所以我猜ImmutableSortedSet也是一样的.
什么是fsharp map的内部实现？是Red Black Tree这里要求的还是AVL tree？
另外MSDN文档为什么不清楚图书馆藏书的实际数据结构是什么？我知道这些是实现细节,即将改变.我的观点是,如果他们不想将库数据类型绑定到某种类型的众所周知的数据结构中,那么至少应该在复杂性方面提供所有方法的性能签名？
解决方法
I am wondering what’s the difference between ImmutableSortedSet and the native FSharp Set?
他们一般非常相似.主要区别在于F#集支持快速集合理论操作(联合,交点和差异).
这是一个简单的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#集合的构造要稍微慢些,搜索速度要稍微快一些,这个集合理论联合运算的速度要快一些.
What is the internal implementation of fsharp map? Is is Red Black Tree as claimed here or AVL tree as found out here?
当两个链接都声明时,F#使用AVL树.
这在上述表现数字的上下文中是相关的. AVL树包含每个分支中子树的最大高度,因此允许子树重新平衡,而不检查整个子树.相比之下,红黑树在每个分支中都包含一位数据,所以重新平衡子树需要遍历整个树,渐近渐近.按照外行人士的说法,两个相同大小的非重叠集合的联合只需要创建一个包含两个现有树的新分支.请注意,BCL API中的联盟甚至无法表达：它处理抽象的IEnumerable而不是具体的集合.
In addition,why MSDN documents don’t state clear what the actual data structure is for the library collection? I know these are implementation details and are about to change. My point is that if they don’t want to bind the library data type to a certain type of well known data structure,they should at least offer a summery of all the methods performance signatures in terms of complexity?
我同意文件中的复杂性会很好.
