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

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

сопс( [] , 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’1′}

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.

Рандомно подобранные статьи с сайта:

Списки в Python 3


Похожие статьи:

admin