Программирование на языке Пролог для искусственного интеллекта



         

Повышение эффективности конкатенации списков за счет совершенствования структуры данных


До сих пор в наших программах конкатенация была определена так:

        конк( [ ], L, L).

        конк( [X | L1], L2, [X | L3] ) :-

                конк( L1, L2, L3 ).

Эта процедура неэффективна, если первый список - длинный. Следующий пример объясняет, почему это так:

        ?-  конк( [а, b, с], [d, e], L).

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

        конк( [а, b, с], [d, e], L)

            конк( [b, с], [d, e], L')                 где L = [a | L']

                конк( [с], [d, e], L")                    где L' = [b | L"]

                    конк( [ ], [d, e], L'")                   где L" = [c | L''']

                        true             (истина)                   где L'" = [d, е]

Ясно, что программа фактически сканирует весь первый список, пока не обнаружит его конец.

А нельзя ли было бы проскочить весь первый список за один шаг и сразу подсоединить к нему второй список, вместо того, чтобы постепенно продвигаться вдоль него? Но для этого необходимо знать, где расположен конец списка, а следовательно, мы нуждаемся в другом его представлении.


Содержание  Назад  Вперед