F #이 연산자 복잡성과 같습니다.

Question

F #에서 기본값 "="(같음) 연산자에 대한 질문이 있습니다. 그것은 사용자가 정의한 union 유형을 비교할 수있게합니다. 문제는 그것의 복잡성은 무엇인가?

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

그것은 분명이 코드 있음 :

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

:

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

이 출력을 생성

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

및 다음 나무 : 예를 들어, 다음과 같은 유형을 살펴 보자

나는 "a = b "이고"a = c "comparsions은 선형 시간이 걸립니다. 그러나 "a = a"은 어떨까요? 그것은 일정한 경우 더 복잡한 구조에 대해 무엇을, 그 같은 :

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

는 전체 D 및 전자 구조를 통해 갈 것인가 아니면 "= A A"에서와 중지됩니다 "C = c "?

Answer 1

F #은 구조적 평등을 사용하지만 .NET의 Equals 기본값은 참조 평등을 사용합니다. 즉, 평 균 비교는 O (N)입니다. 여기서 N은 비교할 개체 그래프의 필드 수입니다.

a = a을 최적화하려면 Equals을 우선 적용하여 참조 평등을 먼저 확인하고 그렇지 않으면 구조적 동등성을 유지하십시오. 자신의 유형에 [<CustomEquality>]으로 주석을 달아야합니다.

the F# source code on github에 상당히 긴 구조적 동일성 구현을 볼 수 있습니다. 호출 계층 구조를 따르려면 GenericEqualityObj on line 1412으로 시작하십시오.

Answer 2

편집 : 원본 답변이 잘못되었습니다.

는

닷넷에서 Equals()의 일반적인 구현은 다음과 같이 작동

• 참조로 두 인스턴스를 비교. 둘 다 동일한 객체를 참조하면 true을 반환하십시오.
• 두 인스턴스의 런타임 유형을 비교하십시오. 다른 경우 false을 반환하십시오.
• 유형의 각 필드를 쌍으로 비교하여 동일한 지 확인하십시오. 일치하지 않으면 false을 반환하고 그렇지 않으면 true을 반환합니다.

어떤 이유로 F #은 첫 번째 단계를 건너 뜁니다. 즉, 시간 복잡성은 항상 선형입니다. 컴파일러는 a 및 b가 같은과 c의 일부 하위 트리가 a의 일부 하위 트리과 동일하며, 그것은 또한 그들이 불변 것을 알고 있다는 것을 알고 있기 때문에

, 그것은 이론적으로 a 및 b 같은 객체를 만들어 일부를 재사용 할 수 그들의 부분의 c. 런타임은 string interning이라는 문자열과 비슷한 문자열을 처리합니다. 하지만 (컴파일되지 않은 코드를 기반으로) 컴파일러는 현재이 작업을 수행하지 않는 것으로 보입니다.