Особенности применения append

автор: Thomas Linder Puls. PDC

Соединение списков Пролога затратно по своей природе. Эта проблема связана с «персистентной» природой прологовых списков. Структура персистентных данных неиз-меняема и неуничтожима при манипулировании с этими данным. Например, если я соединяю два списка, то в результате они продолжают существо-вать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно ис-пользуем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка. Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)). Рассмотрим пример. Имеем бинарное дерево:

Код domains

   binTree = empty(); tree(binTree Left, integer Node, binTree Right).

Мы хотим создать список всех элементов дерева. Вот очевидный способ решения этой задачи, используя предикат append:

Код clauses

   elems(empty()) = []. 
   elems(tree(Left, Node, Right)) = Elems :- 
       LeftElems = elems(Left), 
       RightElems = elems(Right), 
       Elems = append(LeftElems, [Node|RightElems]).

Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева. Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаем список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет со-бой простой путь вниз. Если в дереве N узлов, то мы имеем одну вершину и N-1 элемен-тов в левом поддереве и пустое правое поддерево. В этом уровне, append выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем слу-чае, алгоритм линейный. Оставляю вам доказательство этого утверждения. Лично я никогда не применяю append в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую append. Когда я его вижу, это вызывает насторожен-ность: нет ли проблемы с этим алгоритмом? К счастью, в нашем случае легко избежать использования append. Имеется стандарт-ная «хитрость», которая помогает решить проблему без append с линейной сложностью в худшем случае. Введем вспомогательный предикат, который не только собирает узлы, но и объеди-няет их в список. Звучит это еще более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:

Код clauses

   elems_append(empty(), L) = L. 
   elems_append(tree(Left, Node, Right), L) = M :- 
       RightL = elems_append(Right, L), 
       M = elems_append(Left, [Node|RightL]).

Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идет с конца в на-чало. Этот алгоритм не только не использует append, но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого. Этот предикат не решает исходной проблемы, но следующий предикат делает это:

Код clauses

   elem(Tree) = elem_append(Tree, []).

Т.е. присоединяет пустой список к элементам дерева.