Ответ 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? Является ли это красным черным деревом, как указано здесь, или деревом AVL, как выяснено здесь?
Как указано в ваших ссылках, F # использует деревья AVL.
Это действительно актуально в контексте приведенных выше показателей эффективности. Деревья AVL содержат максимальную высоту поддерева в каждой ветки и, следовательно, позволяют перебалансировать поддеревья без изучения всего поддерева. Напротив, красно-черные деревья содержат один бит данных в каждой ветки, поэтому для поддеревьев поддеревьев требуется, чтобы все деревья пересекались, что было асимптотически медленнее. В непрофессиональных терминах объединение двух одинаковых неперекрывающихся множеств влечет за собой не что иное, как создание новой ветки, содержащей два существующих дерева. Обратите внимание, что Union в API BCL не может даже выразить это: он обрабатывает абстрактный IEnumerable, а не конкретный набор.
Кроме того, почему в документах MSDN не указано, какая фактическая структура данных для коллекции библиотеки? Я знаю, что это детали реализации и вот-вот изменится. Я хочу сказать, что если они не хотят связывать тип данных библиотеки с определенным типом хорошо известной структуры данных, они должны, по крайней мере, предлагать совокупность всех подпрограмм производительности с точки зрения сложности?
Я согласен с тем, что сложности в документах будут хорошими.