Особенности применения 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, []).

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