F # es igual a la complejidad del operador

Question

Tengo una pregunta sobre el operador predeterminado "=" (igual) en F #. Permite comparar tipos de unión definidos por el usuario. La pregunta es: ¿cuál es la complejidad de esto? Por ejemplo, consideremos siguiente tipo:

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

y siguientes árboles:

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)) 

Es obvio que este código:

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

produce esta salida:

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

Espero que el "a = b "y" a = c "comparsions toma el tiempo lineal. Pero ¿qué pasa con "a = a"? Si es constante qué pasa con estructuras más complejas, como aquella:

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

Va a pasar por todo d y estructura e o va a parar en "a = a" y "c = c "?

Answer 1

F # usa igualdad estructural mientras que la implementación predeterminada Equals en .NET usa igualdad de referencia. Esto significa que, en el caso típico, las comparaciones de igualdad son O (N) donde N es el número de campos en los gráficos de objetos que se comparan.

Si desea asegurarse de que a = a está optimizado, puede anular Equals para verificar primero la igualdad de referencia y, de lo contrario, volver a la igualdad estructural. Deberá anotar su tipo con [<CustomEquality>].

Puede ver la implementación bastante larga de la igualdad estructural en the F# source code on github. Para seguir la jerarquía de llamadas, comience por GenericEqualityObj on line 1412.

Answer 2

EDITAR: La respuesta original fue incorrecta.

La aplicación habitual de Equals() en .Net funciona así:

• comparar los dos casos por referencia. Si ambos se refieren al mismo objeto, devuelve true.
• Compare los tipos de tiempo de ejecución de las dos instancias. Si son diferentes, devuelva false.
• Compara cada uno de los campos del tipo pairwise para la igualdad. Si alguno no es igual, devuelva false, de lo contrario, devuelva true.

Por alguna razón, F # omite el primer paso, lo que significa que la complejidad del tiempo es siempre lineal.

Desde el compilador sabe que a y b son los mismos y algunos subárboles de c son los mismos que algunos subárboles de a, y también se sabe que son inmutables, que en teoría podría hacer a y b el mismo objeto y reutilizar algunos de sus partes en c. El tiempo de ejecución hace algo similar con cadenas, llamado string interning. Pero (basado en el código descompilado) parece que el compilador actualmente no hace esto.