F# è uguale alla complessità dell'operatore

Question

Ho una domanda su predefinito "="(uguale) operatore in f#. Permette di confrontare i tipi di unione definiti dall'utente. La domanda è: qual è la complessità di esso? Ad esempio, consideriamo il seguente tipo:

type Tree<'a> =
  | Nil
  | Leaf of 'a
  | Node of Tree<'a> * Tree<'a>

e seguendo gli alberi:

let a : Tree<int> = Node (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), Node (Leaf 6, Nil))
let b : Tree<int> = Node (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), Node (Leaf 6, Nil))
let c : Tree<int> = Node (Node (Node (Leaf 1, Leaf 2), Nil), Node (Node (Leaf 3, Node (Leaf 4, Leaf 5)), Leaf 6))

È ovvio che questo codice:

printfn "a = b: %b" (a = b)
printfn "a = c: %b" (a = c)
printfn "a = a: %b" (a = a)

produce questo output:

a = b: true
a = c: false
a = a: true

Mi aspetto che il "a = b" e "a = c"Le comparsioni richiedono il tempo lineare. Ma che ne dici di"a = a"? Se è costante che dire delle strutture più complesse, come quella:

let d : Tree<int> = Node (a, c)
let e : Tree<int> = Node (a, c)

Passerà intero d e e struttura o si fermerà a "a = a" e "c = c"?

Answer 1

F# usa l'uguaglianza strutturale mentre il valore predefinito Equals L'implementazione in .NET utilizza l'uguaglianza di riferimento. Ciò significa, nel caso tipico, i confronti di uguaglianza sono SU) dove N è il numero di campi nei grafici degli oggetti confrontati.

Se vuoi assicurarti a = a è ottimizzato, puoi sovrascrivere Equals Per verificare prima l'uguaglianza di riferimento e rientrare in caso di uguaglianza strutturale. Dovrai annotare il tuo tipo con [<CustomEquality>].

Puoi vedere l'implementazione piuttosto lunga dell'uguaglianza strutturale in Il codice sorgente F# su GitHub. Per seguire la gerarchia delle chiamate inizia con GenericEqualityObj sulla riga 1412.

Answer 2

MODIFICARE: La risposta originale era sbagliata.

La solita implementazione di Equals() In .NET funziona in questo modo:

• Confronta le due istanze per riferimento. Se entrambi si riferiscono allo stesso oggetto, restituisce true.
• Confronta i tipi di runtime delle due istanze. Se sono diversi, ritorna false.
• Confronta ciascuno dei campi del tipo a coppie a coppie per l'uguaglianza. Se qualcuno non è uguale, restituisce false, altro ritorno true.

Per qualche ragione, F# salta il primo passo, il che significa che la complessità temporale è sempre lineare.

Dal momento che il compilatore lo sa a e b sono uguali e alcuni sottostrutici di c sono uguali a alcuni sottostrutici di a, e sa anche che sono immutabili, potrebbe teoricamente fare a e b lo stesso oggetto e riutilizzare alcune delle loro parti in c. Il runtime fa qualcosa di simile con le stringhe, chiamate String Interning. Ma (basato su codice decompilato) sembra che il compilatore non lo faccia.