Qual è la differenza tra `ImmutableSortedSet` e fsharp` Set`?

Question

BCL has introduced a group of Immutable Collections

Mi chiedo qual è la differenza tra ImmutableSortedSet e FSharp nativo Set? Sembra che le performance signature di entrambi siano simili. Inoltre ho visto da qualche parte che lo SortedSet è implementato come un albero nero rosso, quindi suppongo che lo ImmutableSortedSet faccia lo stesso.

Qual è l'implementazione interna di fsharp map? È Red Black Tree come rivendicato qui o AVL tree come trovato qui?

Inoltre, perché i documenti MSDN non indicano chiaramente quale sia la struttura dati effettiva per la raccolta di librerie? So che questi sono dettagli di implementazione e stanno per cambiare. Il mio punto è che se non vogliono associare il tipo di dati della libreria a un certo tipo di struttura dati ben nota, dovrebbero almeno offrire un riepilogo di tutti i metodi di firma delle prestazioni in termini di complessità?

Answer 1

Mi chiedo qual è la differenza tra ImmutableSortedSet e il nativo FSharp Set?

Sono generalmente molto simili. La differenza principale è che F # Set supporta operazioni teoriche di impostazione rapida (unione, intersezione e differenza).

Ecco un semplice programma di F #, che misura le prestazioni di alcune operazioni comuni:

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 

Sulla mia macchina, ottengo:

  BCL ImmutableSortedSet F# Set 
add    2.6s   3.0s 
contains   2.1s   1.9s 
union    1.1s   0.00004s 

Così la F # Set è leggermente più lento di costruire e un po 'più veloce per la ricerca, ma ordini di grandezza più veloci per l'operazione di unione teorica impostata.

Qual è l'implementazione interna della mappa fsharp? È l'albero nero rosso come rivendicato qui o l'albero AVL come scoperto qui?

Come indicano entrambi i collegamenti, F # utilizza alberi AVL.

Questo è effettivamente rilevante nel contesto delle prestazioni sopra riportate. Gli alberi AVL contengono l'altezza massima di una sottostruttura in ciascun ramo e, pertanto, consentono di riequilibrare i sottoalberi senza esaminare l'intera struttura secondaria. Al contrario, gli alberi rosso-neri contengono un singolo bit di dati in ciascun ramo, quindi i sottoalberi di bilanciamento richiedono l'attraversamento di interi alberi che è asintoticamente più lento. In parole povere, l'unione di due insiemi non sovrapposti di uguali dimensioni comporta poco più della creazione di un nuovo ramo contenente i due alberi esistenti. Si noti che il Union nell'API BCL non è nemmeno in grado di esprimere questo: gestisce un abstract IEnumerable anziché un set concreto.

Inoltre, perché i documenti MSDN non indicano chiaramente quale sia la struttura dati effettiva per la raccolta di librerie? So che questi sono dettagli di implementazione e stanno per cambiare. Il mio punto è che se non vogliono associare il tipo di dati della libreria a un certo tipo di struttura dati ben nota, dovrebbero almeno offrire un riepilogo di tutti i metodi di firma delle prestazioni in termini di complessità?

Sono d'accordo sul fatto che le complessità nei documenti sarebbero buone.

Answer 2

I tipi F # Set e Map sono implementati con alberi AVL.

Non so circa la documentazione MSDN, dovreste chiedere al # team F in merito a questo :)

In ogni caso, rosso-nero alberi e alberi AVL hanno la stessa complessità computazionale per la loro principale operazioni. In pratica, hanno caratteristiche di performance diverse che possono portarti a scegliere l'una o l'altra per la tua specifica applicazione - Gli alberi Red-Black hanno un inserimento/eliminazione più veloce perché non hanno bisogno di fare il ribilanciamento dell'albero, ma il recupero è più veloce negli alberi AVL grazie a quel bilanciamento aggiuntivo che esegue per inserimento/eliminazione. Immagino che questo è il motivo per cui gli alberi AVL sono stati scelti per la mappa F # e le implementazioni di Set - una mappa/gruppo viene solitamente creato una volta (cioè, non modificato), quindi interrogato ripetutamente.

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

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