F＃はオペレーターの複雑さに等しくなります

Question

デフォルトについて質問があります」="（equals）f＃。ユーザー定義の組合タイプを比較できます。問題は次のとおりです。たとえば、次のタイプを考えてみましょう。

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

そして次の木：

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

このコードは明らかです。

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

この出力を生成します：

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

私はそれを期待していますa = b" と "a = c「コンパーは線形時間がかかります。しかし、どうですか」a = a「？それが一定の場合、そのようなより複雑な構造についてはどうでしょうか：

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

それは全体を通過しますか d と e 構造またはそれが停止するでしょう」a = a" と "c = c"?

Answer 1

F＃は構造的平等を使用し、デフォルトを使用します Equals .NETでの実装は、参照平等を使用します。これは、典型的な場合、平等比較は オン） どこ n 比較されるオブジェクトグラフのフィールドの数です。

確実にしたい場合 a = a 最適化されているため、オーバーライドできます Equals 最初に参照平等を確認し、それ以外の場合は構造的平等に頼ります。タイプに注目する必要があります [<CustomEquality>].

構造的平等のかなり長い実装を見ることができます GithubのF＃ソースコード. 。コール階層をフォローするには、開始します GenericEqualityObj 1412行目.

Answer 2

編集： 元の答えは間違っていました。

の通常の実装 Equals() .NETでは次のように動作します：

• 参照によって2つのインスタンスを比較します。両方が同じオブジェクトを参照している場合は、返します true.
• 2つのインスタンスのランタイムタイプを比較します。それらが違う場合は、戻ります false.
• 等価については、タイプペアワイズの各フィールドを比較します。存在しない場合は、返します false, 、そうでなければ戻ってきます true.

何らかの理由で、F＃は最初のステップをスキップします。つまり、時間の複雑さは常に線形です。

コンパイラはそれを知っているので a と b 同じものであり、いくつかのサブツリーです c いくつかのサブツリーと同じです a, 、そしてそれは彼らが不変であることを知っています、それは理論的には a と b 同じオブジェクトとその一部の部分を再利用します c. 。ランタイムは、呼ばれる文字列で似たようなことをします ストリングインターン. 。しかし（逆コンパイルコードに基づいて）コンパイラは現在これを行っていないようです。