F # равно сложности оператора - PullRequest
Новая
       26

F # равно сложности оператора

5 голосов
/ 16 января 2012

У меня есть вопрос об операторе по умолчанию " = " (равно) в 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"

Ответы [ 2 ]

4 голосов
/ 16 января 2012

F # использует структурное равенство, тогда как стандартная реализация Equals в .NET использует равенство ссылок. Это означает, что в типичном случае сравнения равенства равны O (N) , где N - количество полей в сравниваемых графах объектов.

Если вы хотите обеспечить оптимизацию a = a, вы можете переопределить Equals, чтобы сначала проверить на равенство ссылок, а в противном случае использовать структурное равенство. Вам нужно будет пометить свой тип с помощью [<CustomEquality>].

Вы можете увидеть довольно длинную реализацию структурного равенства в исходном коде F # на github . Чтобы следовать иерархии вызовов, начните с GenericEqualityObj в строке 1412 .

0 голосов
/ 16 января 2012

РЕДАКТИРОВАТЬ: Исходный ответ был неправильным.

Обычная реализация Equals() в .Net работает так:

  • Сравните два экземплярапо ссылке.Если они оба ссылаются на один и тот же объект, верните true.
  • Сравните типы времени выполнения двух экземпляров.Если они разные, верните false.
  • Сравните каждое из полей типа попарно на равенство.Если какие-либо не равны, вернуть false, иначе вернуть true.

По какой-то причине F # пропускает первый шаг, что означает, что сложность времени всегда линейна.

Поскольку компилятор знает, что a и b одинаковы, а некоторые поддеревы c совпадают с некоторыми поддеревами a, и он также знает, что они неизменны, он теоретически может сделать a иb один и тот же объект и повторно используйте некоторые его части в c.Среда выполнения делает нечто похожее со строками, называемое string interning .Но (основываясь на декомпилированном коде) кажется, что компилятор в настоящее время этого не делает.

...