F# 等于运算符复杂度
我对 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<” /em>”和“c = c”？
I have a question about default "=" (equals) operator in F#. It allows to compare user-defined union types. The question is: what's the complexity of it? For example, let's consider following type:
type Tree<'a> =
| Nil
| Leaf of 'a
| Node of Tree<'a> * Tree<'a>
and following trees:
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))
It is obvious that this code:
printfn "a = b: %b" (a = b)
printfn "a = c: %b" (a = c)
printfn "a = a: %b" (a = a)
produces this output:
a = b: true
a = c: false
a = a: true
I expect that the "a = b" and "a = c" comparsions takes the linear time. But what about "a = a"? If it is constant what about more complex structures, like that one:
let d : Tree<int> = Node (a, c)
let e : Tree<int> = Node (a, c)
Will it go through whole d and e structure or will it stop at "a = a" and "c = c"?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
F# 使用结构相等，而 .NET 中的默认
Equals实现使用引用相等。这意味着，在典型情况下，相等比较的时间为 O(N)，其中 N 是要比较的对象图中的字段数。如果您想确保
a = a得到优化，您可以重写Equals以首先检查引用相等性，否则再依靠结构相等性。您需要使用[] 注释您的类型。您可以在 github 上的 F# 源代码。要遵循调用层次结构，请从 第 1412 行上的
GenericEqualityObj。F# uses structural equality whereas the default
Equalsimplementation in .NET uses reference equality. This means, in the typical case, equality comparisons are O(N) where N is the number of fields in the object graphs being compared.If you want to ensure
a = ais optimized, you can overrideEqualsto check for reference equality first, and fall back on structural equality otherwise. You'll need to annotate your type with[<CustomEquality>].You can see the rather lengthy implementation of structural equality in the F# source code on github. To follow the call hierarchy start with
GenericEqualityObjon line 1412.编辑：原来的答案是错误的。
.Net 中
Equals()的通常实现方式如下：true。false。false，否则返回true。由于某种原因，F# 跳过第一步，这意味着时间复杂度始终是线性的。
由于编译器知道
a和b是相同的，并且c的某些子树与a的某些子树相同>，而且它也知道它们是不可变的，理论上它可以使a和b成为同一个对象，并在c中重用它们的一些部分。运行时对字符串执行类似的操作，称为字符串驻留。但是（基于反编译的代码）编译器目前似乎没有这样做。EDIT: The original answer was wrong.
The usual implementation of
Equals()in .Net works like this:true.false.false, else returntrue.For some reason, F# skips the first step, which means the time complexity is always linear.
Since the compiler knows that
aandbare the same and some subtrees ofcare same as some subtrees ofa, and it also knows that they are immutable, it could theoretically makeaandbthe same object and reuse some of their parts inc. The runtime does something similar with strings, called string interning. But (based on decompiled code) it seems the compiler currently doesn't do this.