Эффективное решение проблемы одинаковой границы для бинарных деревьев

Если вы перенесете работу на функции модификации дерева, вы можете сохранить знаковый счетчик «unmatchedcount», скажем, листьев на дереве 1, а не на дереве 2, минус на дереве 2 и не на дереве 1 соответственно, тогда вы сможете узнать за время O (1), если они совпало или нет.

Предложение: используйте swi-prolog.org/pldoc/man?section=threadcom и выполняйте каждый обход в отдельном потоке (т. е. создайте 2 потока), при этом основной поток проверит, что листья, возвращенные с помощью thread_get_message, равны (хотя и в разные заказы). Приемлемо ли решение, специфичное для swi-prolog?

Второй извлекает выгоду из некоторых микрооптимизаций. У него никогда не было лучшего большого О. Поиск микрооптимизаций для первого в случае, когда второй работает лучше всего, будет зависеть от языка, платформы и данных.

@brebs Да, решение для swi-prolog было бы приемлемым. Спасибо за предложение.

@SimonGoater Создание/модификация дерева направлена ​​только на автоматическую генерацию данных для эмпирического сравнения предикатов sf_1/2 e sf_2/2. Два предложенных решения не должны создавать или изменять деревья, а лишь проверять, имеют ли они одинаковую полосу.

@btilly Точно! Очевидно, что оба решения в худшем случае равны O(n), поскольку невозможно сравнить все n листьев двух деревьев за меньшее время (когда я говорю «быстрее», я не имею в виду асимптотически быстрее), и фактически , желаемое решение должно быть специфичным для языка Пролог (именно поэтому вопрос помечен как пролог).

Интересный факт: бывают случаи, когда ускорение может составлять от O(N) до O(1)!

Альтернатива тредам: продолжения с разделителями: swi-prolog.org/pldoc/man?section=delcont

просто примечание: ваш sf_1 не «собирает листья одного дерева в список, а затем сравнивает их с листьями другого дерева». он собирает листья каждого дерева в свой список независимо, а затем, построив второй список до его головного элемента, сравнивает второй список с первым списком. это связано с тем, что порядок целей в walk -- A1 полностью независим от Xs. только когда будет достигнут самый левый лист, у нас будет { walk(L, A1, Xs) = walk(leaf(X), A, [X|A]) } === { L=leaf(X),A1=A,Xs=[X|A] } === { L=leaf(X), Xs=[X|A1] }.

(продолжение) Это потому, что списки строятся снизу вверх. если бы списки строились сверху вниз, то второй walk, то есть обход по второму дереву с полностью построенным списком листьев из первого дерева, имел бы шанс потерпеть неудачу на первом несовпадающем листе из второго дерева. конечно, ему все равно придется сначала полностью пройти через первое дерево.

Этот -2 кажется неоднозначным примером — демонстрирует ли он, что обход дерева не гарантирует упорядоченный список, или демонстрирует явно неправильное значение?

Я не вижу, что двусмысленного в 1,2,3 против 1,-2,3.

@false, вы приняли ответ, это более или менее то, что я имел в виду. Я не понимаю, что в этом плохого? Кстати, это «закапывание» в самый левый лист — та же идея, что и идея «суслика» Джона Маккарти, создателя LISP, за исключением того, что он на самом деле поворачивает дерево вправо, в то время как вы создаете стек, но это тоже самое.

что с этим не так? Это могло бы быть намного лучше с точки зрения прекращения.

Или стоимость может быть постоянной, если она равна O(max(N1,N2))

Пример: ?- sf_(leaf(X),fork(_,_)). пока весь цикл, но это может привести к сбою. Таким образом, все остальные экземпляры представляют собой гигантские деревья с более чем одним fork.

...кстати, даже ?- sf_(leaf(X),T)., очевидно, должно прекратиться.

@false, поэтому теперь мы не видим вопрос, на который были опубликованы новые ответы, то есть требования к награде. Могу ли я предложить вместо этого в следующий раз опубликовать новый, отдельный вопрос, с обратной ссылкой на исходную запись (например, в данном случае), если это необходимо. Совершенно нормально назначить награду за собственный вопрос, чтобы «привлечь внимание к вопросу». таким образом сохраняются как исходный, так и последующие вопросы, и каждый ответ отображается под отдельным вопросом. Спасибо.

@Will, согласен с отсутствующим текстом, который был примером вопроса ОП выше (то есть лучшее завершение, что означает лучшее O). Но снова публиковать новый вопрос при нынешнем низком трафике? Подумайте об этом, я намерен назначить еще одну награду за этот вопрос... Вопрос о награде тоже поставлю в качестве комментария.

@false это действительно не общепринятый способ. подход SO предполагает, что ответы на вопрос отвечают на него, а не на что-то еще. то, как обстоят дела сейчас, действительно сбивает с толку. каждый раз, когда вы публикуете награду за существующий вопрос с новыми требованиями, создается эта проблема. трафик или его отсутствие — это ортогональный вопрос. Я думаю, если вы зададите вопрос, люди проявят интерес. если нет, вы бы добавили бонус, и они это заметят. комментарии должны быть эфемерными. это комментарии, а не содержимое.

Все мои награды — это уточнения исходных вопросов. ОП просил не обязательно асимптотически быстрее.

... однако, как вам кажется, @Will больше занимался SO-контролем, чем программированием.

Я просто обратился к Вам со своим мнением. Вот для чего нужны комментарии.

Удаление предиката next/3 и замена предложения stepping(leaf(X), T2s0, T2s) :- next(X, T2s0, T2s). на stepping(leaf(X), [T|Ts0], T2s ) :- t_next(T, X, Ts0, T2s). делает реализацию еще быстрее.

(Это то, что я имел в виду под разворачиванием next/3)

Интересный! Предотвращая создание списка для второго дерева, предикат sf_1b/2 работает быстрее, чем sf_1/2, когда деревья не имеют одинаковых границ; однако, если у них одинаковая бахрома, sf_1b/2 может быть немного медленнее, чем sf_1/2.

@Абду: Вы удаляете ту самую информацию, которая представляет интерес для всех, кто понимает этот ответ. sf_1b не оптимальное решение.

(Это поможет придерживаться соглашения об именах. trees предлагает список tree)

Зафиксированный. Я надеюсь (не уверен), что теперь это достаточно общее.

(кажется, правильно) ?- T1 = fork(leaf(1),fork(leaf(2),leaf(3))), tree_equal(T1,T2), false. loops. это не требовалось для награды, если вы найдете улучшение, используйте другой ответ.

Вот тест: ?- numbered_from(L,1),tree_leaves(T,L), ( true ; tree_equal(T,_), false ). выполнит цикл для поиска простейшего контрпримера, если он есть.

Также обратите внимание, что ваш member_exists/2 по-прежнему выдает несколько ответов из-за переменных _. ?- member_exists(fork(_,_),[fork(leaf(1),leaf(2)),fork(leaf(3),‌​leaf(4))]). true ; true ; false.

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

Найдите его в SO или в Google :-)

И еще: было бы полезно, если бы вы придерживались оригинальных названий, примерно sf_br99 или около того, чтобы все версии можно было загружать одновременно без какого-либо дополнительного модуляции.

Прекращение в порядке, но теперь оно неполное. ?- T = fork(leaf(1),fork(leaf(2),fork(leaf(3),leaf(4)))), T2 = fork(fork(leaf(1),fork(leaf(2),leaf(3))),leaf(4)), tree_equal(T,T2). false, unexpected.

Наконец-то достигнута полнота и завершение.