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

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