Эффективная функция равенства на деревьях
Несколько дней назад мне дали следующий вопрос интервью. Он был описан со стандартным кодом ML, но я был вправе отвечать на языке по своему выбору (я выбрал Python):
У меня есть тип:
datatype t = Leaf of int | Node of (t * t)
и функция
f
с сигнатуройval f: int -> t
Вам нужно написать функцию равную, которая проверяет,
equals
ли два дерева.f
–O(n)
, и это «наихудшая возможная вещь» для временной сложности вашей функцииequals
. Записатьequals
, чтобы он никогда не экспоненциально поn
, аргументf
.
Пример f
который был предоставлен:
fun fn = if n = 0 then Leaf(0) else let val subtree = f (n - 1) in Node (subtree, subtree) end
который создает экспоненциально большое дерево в O(n)
времени, поэтому equals (f(n), f(n))
для наивной equals
реализации, линейной по числу узлов дерева является O(2^n)
.
Я произвел что-то вроде этого:
class Node: def __init__(self, left, right): self.left = left self.right = right class Leaf: def __init__(self, value): self.value = value def equals(left, right): if left is right: return True try: return left.value == right.value except ValueError: pass try: return equals(left.left, right.left) and equals(left.right, right.right) except ValueError: return False
который работал на примере f
, предоставленном интервьюером, но не прошел в общем случае « f
делает худшее возможное». Он привел пример, который я не помню, что прервала мою первую попытку. Я немного окунулся и в итоге сделал что-то похожее на это:
cache = {} def equals(left, right): try: return cache[(left, right)] except KeyError: pass result = False try: result = left.value == right.value except ValueError: pass try: left_result = equals(left.left, right.left) right_result = equals(left.right, right.right) cache[(left.left, right.left)] = left_result cache[(left.right, right.right)] = right_result result = left_result and right_result except ValueError: pass cache[(left, right)] = result return result
но я чувствовал, что это был неуклюжий хак, и это явно не то, что искал интервьюер. Я подозреваю, что есть элегантный способ избежать перекомпоновки поддеревьев – что это?
- Алгоритм поиска подмножества из списка, который выполняет ограничение
- Вычислить STD вручную с помощью Groupby Pandas DataFrame
- Как сделать цветопередачу из цветовой палитры
- алгоритм сжатия группы (пары строк)
- Создание всех 5 карточных покерных рук
Ваше решение как таковое является O (n ^ 2) по внешнему виду. Мы можем сделать это O (n), используя memoization для идентичности одного дерева, а не пару деревьев:
memoByVal = {} memoByRef = {id(None): 0} nextId = 1 # produce an integer that represents the tree's content def getTreeId(tree): if id(tree) in memoByRef: return memoByRef[id(tree)] # nodes are represented by the (left, right, value) combination # let's assume that leafs just have left == right == None l, r = getTreeId(tree.left), getTreeId(tree.right) if (l, r, tree.value) not in memoByVal: memoByVal[l, r, tree.value] = nextId nextId += 1 res = memoByVal[l, r, tree.value] memoByRef[id(tree)] = res return res # this is now trivial def equals(a, b): return getTreeId(a) == getTreeId(b)
Вы можете использовать хеш для создания реплик обоих деревьев в линейном времени, а затем сравнить их для равенства в постоянное время.
Вот пример хеширования в sml.
https://github.com/jhckragh/SMLDoc/tree/master/smlnj-lib/HashCons
Обновить:
См. Комментарии. Я был слишком поспешным в этом ответе. Я не думаю, что можно создать реплику в линейном времени. Вам нужно будет начать с типа хеш-consed и использовать только эти конструкторы в f.
- Как один итеративно записывает сортировку слияния?
- Python: найдите, если точка лежит на границе многоугольника
- Сложность времени с циклами while
- Разделение кусковой последовательности на четные посылки?
- Список минимальных пар из пары списков
- Подходящие подкомпоны
- Алгоритм решателя Quiddler
- LDA в python с использованием sklearn
- Алгоритм поиска приблизительной площади земли через решетку высоты?