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

Question

기본값에 대해 질문이 있습니다.=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)

통째로 통과될까 디 그리고 이자형 구조인가요, 아니면 '에서 멈출까요?a = a" 그리고 "c = c"?

Answer 1

F#은 구조적 동등성을 사용하지만 기본값은 Equals .NET의 구현에서는 참조 동등성을 사용합니다.이는 일반적인 경우 동등 비교가 다음과 같다는 것을 의미합니다. 에) 어디 N 비교되는 객체 그래프의 필드 수입니다.

보장하고 싶다면 a = a 최적화되어 있으므로 재정의할 수 있습니다. Equals 참조 동등성을 먼저 확인하고 그렇지 않으면 구조적 동등성을 확인합니다.유형에 다음과 같은 주석을 달아야 합니다. [<CustomEquality>].

구조적 평등의 다소 긴 구현을 볼 수 있습니다. github의 F# 소스 코드.통화 계층 구조를 따르려면 다음으로 시작하세요. GenericEqualityObj 1412번 라인에서.

Answer 2

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

일반적인 구현 Equals() .Net에서는 다음과 같이 작동합니다.

• 두 인스턴스를 참조로 비교합니다.둘 다 동일한 객체를 참조하는 경우 반환 true.
• 두 인스턴스의 런타임 유형을 비교합니다.다르면 반품하세요 false.
• 해당 유형의 각 필드가 동일한지 쌍으로 비교합니다.동일하지 않은 경우 반환 false, 그렇지 않으면 반환 true.

어떤 이유로 F#은 첫 번째 단계를 건너뜁니다. 이는 시간 복잡도가 항상 선형임을 의미합니다.

컴파일러는 그것을 알고 있기 때문에 a 그리고 b 동일하며 일부 하위 트리는 c 의 일부 하위 트리와 동일합니다. a, 그리고 그것들이 불변이라는 것도 알고 있습니다. 이론적으로 다음을 만들 수 있습니다. a 그리고 b 동일한 개체를 사용하고 해당 부분의 일부를 재사용합니다. c.런타임은 문자열과 비슷한 작업을 수행합니다. 문자열 인턴.그러나 (디컴파일된 코드에 따르면) 컴파일러는 현재 이 작업을 수행하지 않는 것 같습니다.