Повышение эффективности конкатенации списков с использованием разностных списков

Б программах, применяемых до сих пор, алгоритм конкатенации списков был за­программирован следующим образом:

сопс([], L, L).

conci, [X | LI], L2, [X | L3]):-conc(LI, L2, L3).

Такая программа является неэффективной, если первый список имеет большую длину. Следующий пример показывает, с чем это связано:

?- сопо([a,b,c], |d,в], Lj.

Этот вопрос вырабатывает следующую последовательность целей:

conci [a,b,c], [d,e], L!

conci [b,c], [d,e], L'), где L = [a | L']

Conc([c], [d,e], L"), где L' -~ [b | L' ' ]

conci [], [d,e], L'^p')r где L"= [c I L'¹'}

true, где L'' ' = [d,e]

Из этого становится ясно, что данная программа, по сути, постоянно просматри­вает первый список до тех пор, пока не встретится пустой список.

Но нельзя ли на первом этапе вместо постепенной проработки первого списка пропустить весь первый список и добавить к нему второй список? Для этого необхо­димо знать, где находятся конец списка; иными словами, требуется другое представ­ление для списков. Одно из решений состоит в использовании структуры данных, называемой разностными списками. При этом список представляется з виде пары списков. Например, список

[a,b,d]

может быть представлен с помощью следующих двух списков:

L1 = [ a,b,c,d,е ] L2 - [d,e]

Такая пара списков, которая сокращенно обозначается как L1-L2, представляет "разницу" между L1 и L2. Безусловно, подобная конструкция может применяться лишь при условии, что список L2 — суффикс списка L1. Следует отметить, что один и тот же список может быть представлен с помощью нескольких разностных пар. Поэтому, например, список [а, Ь, с] может быть представлен следующим образом:

[а,Ь,с]-[]

или

[а,Ь, с, d, e] - [d, e ]

Глава В, Стиль и методы программирования

или [а,Ь,с_г«3,е | T] - Id,e | T]

Или

[а,ь,с | t) - T

где Т — любой список. Пустой список представляется с помощью любой пары в фор­ме L-L.

Поскольку второй член пары обозначает конец списка, этот конец становится не­посредственно доступным. Поэтому разностные списки могут использоваться для эф­фективной реализации конкатенации. Такой метод иллюстрируется на рис. 8.1. Со­ответствующее отношение конкатенации.можно перевести на язык Prolog как сле­дующий факт:

ccncati А1 - 21, Z1 - 22, А1 - Z2>.

М

L1

 

Z2

Z1 А2

' 1	'
L2	.. ■-■■ ----------------------- П

13 L3

Лс. 3.1. Конкатенация списков, представленных разно­стными парами; список L1 представлен как A1-Z1, 12 — как A2-Z2, а результат, 13, представлен как А1-Z2, где выражение Z1 - А2 должно быть истинным

Ниже приведен пример использования отношения concat для конкатенации спи­ска [а,Ь,с], представленного парой [а,Ь,с I Т1] - Т1, и списка [d, е-, пред­ставленного как [d,e I Т2] - Т2.?- concat* [а,Ь,с \ T1J - Tl, [d,e | Т2 J - Т2, L!.

Конкатенация выполняется путем согласования этой цели с предложением, опре­деляющим процедуру concat, что приводит к получению следующего результата:

Т1 = [d,e ] Т2]

Г. = [a,b,c,d, G | 12] - Т2

Благодаря его эффективности описанный метод конкатенации списков с помощью разностных списков находит очень широкое применение, хотя и не может использо­ваться н столь разнообразных вариантах, как обычная процедура cone.