Назад | Содержание| Вперёд 8. 5. Эффективность Существует несколь...

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

8. 5. Эффективность

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

Традиционная архитектура вычислительных машинне очень хорошо приспособлена для реализациипрологовского способа выполнения программ,предусматривающего достижение целей изнекоторого списка. Поэтому ограниченностьресурсов по времени и пространству сказывается вПрологе, пожалуй, в большей степени, чем вбольшинстве других языков программирования.Вызовет ли это трудности в практическихприложениях, зависит от задачи. Фактор временипрактически не имеет значения, еслипролог-программа, которую запускают по несколькораз в день, занимает 1 секунду процессорноговремени, а соответствующая программа накаком-либо другом языке, скажем на Фортране, - 0.1секунды. Разница в эффективности становитсясущественной, если эти две программы требуют 50 и 5минут соответственно.

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

естественным

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

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

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

Повышение эффективности поиска путем скорейшего отказа от ненужного перебора и от вычисления бесполезных вариантов.

Применение cтруктур данных, более приспособленных для представления объектов программы, с целью реализовать операции над ними более эффективно.

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

8. 5. 1. Повышение эффективностирешения задачи о восьми ферзях

В качестве простого примера повышенияэффективности давайте вернемся к задаче о восьмиферзях (см. рис. 4.7). В этой программе Y-координатыферзей перебираются последовательно - длякаждого ферзя пробуются числа от 1 до 8. Этотпроцесс был запрограммирован в виде цели

принадлежит( Y, [1, 2, 3,4, 5, 6, 7, 8] )

Процедура принадлежит работает так:вначале пробует Y = 1, затем Y = 2, Y = 3 и т.д. Посколькуферзи расположены один за другим в смежныхвертикалях доски, очевидно, что такой порядокперебора не является оптимальным. Дело в том, чтоферзи, расположенные в смежных вертикалях будутбить друг друга, если они не будут разнесены повертикали на расстояние, превышающее, по крайнеймере одно поле. В соответствии с этим наблюдениемможно попытаться повысить эффективность, простоизменив порядок рассмотрениякоординат-кандидатов. Например:

принадлежит( Y, [1, 5, 2,6, 3, 7, 4, 8] )

Это маленькое изменение уменьшит время,необходимое для нахождения первого решения, в 3-4раза.

В следующем примере такая же простая идея,связанная с изменением порядка, превращаетпрактически неприемлемую временную сложность втривиальную.

8. 5. 2. Повышение эффективностипрограммы раскраски карты

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

Пусть карта задана отношением соседства

соседи( Страна,Соседи)

где Соседи - список стран, граничащихсо страной Страна. При помощи этогоотношения карта Европы с 20-ю странами будетпредставлена (в алфавитном порядке) так:

соседи( австрия,[венгрия, запгермания, италия,

лихтенштейн, чехословакия,

швейцария, югославия]),

соседи( албания,[греция, югославия]).

соседи( андорра,[испания, франция]).

. . .

Решение представим в виде списка пар вида

Страна / Цвет

которые устанавливают цвет для каждой странына данной карте. Для каждой карты названия странвсегда известны заранее, так что задача состоит внахождении цветов. Таким образом, для Европызадача сводится к отысканию подходящейконкретизации переменных C1, C2, СЗ и т.д. в списке

[австрия/C1,албания/С2, андорра/С3, . . .]

Теперь определим предикат

цвета(СписЦветСтран)

который истинен, если СписЦветСтранудовлетворяет тем ограничениям, которыеналожены на раскраску отношением соседи.Пусть четырьмя цветами будут желтый, синий,красный и зеленый. Условие запрета раскраскисоседних стран в одинаковый цвет можносформулировать на Прологе так:

цвета( [ ]).

цвета( [Страна/Цвет |Остальные] ) :-

цвета( Остальные),

принадлежит(Цвет, [желтый, синий, красный, зеленый]),

not(принадлежит( Страна1/Цвет, Остальные),

сосед( Страна, Страна1) ).

сосед( Страна,Страна1) :-

соседи( Страна, Соседи),

принадлежит( Страна1, Соседи).

Здесь принадлежит( X, L) - как всегда,отношение принадлежности к списку. Для простыхкарт с небольшим числом стран такая программабудет работать. Что же касается Европы, то здесьрезультат проблематичен. Если считать, что мырасполагаем встроенным предикатом setof,то можно попытаться раскрасить карту Европыследующим образом. Определим сначалавспомогательное отношение:

страна( С) :- соседи(С, _ ).

Тогда вопрос для раскраски карты Европы можносформулировать так:

?- sеtоf( Стр/Цвет,страна( Стр), СписЦветСтран),

цвета(СписЦветСтран).

Цель setof - построить "шаблон"списка СписЦветСтран, в котором вэлементах вида страна/ цвет вместо цветов будутстоять неконкретизированные переменные.Предполагается, что после этого цель цветаконкретизирует их. Такая попытка скорее всегопотерпит неудачу вследствие неэффективностиработы программы.

Тщательное исследование способа, при помощикоторого пролог-система пытается достичь цели цвета,обнаруживает источник неэффективности. Странырасположены в списке в алфавитном порядке, а онне имеет никакого отношения к их географическимсвязям. Порядок, в котором странам приписываютсяцвета, соответствует порядку их расположения всписке (с конца к началу), что в нашем случае никакне связано с отношением соседи. Поэтомупроцесс раскраски начинается в одном концекарты, продолжается в другой и т.д., перемещаясьпо ней более или менее случайно. Это легко можетпривести к ситуации, когда при попыткераскрасить очередную страну окажется, что онаокружена странами, уже раскрашенными во всечетыре доступных цвета. Подобные ситуацииприводят к возвратам, снижающим эффективность.

Ясно поэтому, что эффективность зависит отпорядка раскраски стран. Интуиция подсказываетпростую стратегию раскраски, которая должна бытьлучше, чем случайная: начать со страны, имеющейиного соседей, затем перейти к ее соседям, затем -к соседям соседей и т.д. В случае Европы хорошимкандидатом для начальной страны являетсяЗападная Германия (как имеющая наибольшееколичество соседей - 9). Понятно, что припостроении шаблона списка элементов видастрана/цвет Западную Германию следует поместитьв конец этого списка, а остальные страны -добавлять со стороны его начала. Таким образом,алгоритм раскраски, который начинает работу сконца списка, в начале займется ЗападнойГерманией и продолжит работу, переходя от соседак соседу.

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

Можно было бы построить такой правильноупорядоченный список стран вручную, но в этом нетнеобходимости. Эту работу выполнит процедура создспис.Она начинает построение с некоторой указаннойстраны (в нашем случае - с Западной Германии) исобирает затем остальные страны в список подназванием Закрытый. Каждая странасначала попадает в другой список, названный Открытый,а потом переносится в Закрытый. Всякийраз, когда страна переносится из Открытыйв Закрытый, ее соседи добавляются в Открытый.

создспис( Спис) :-

собрать( [запгермания], [ ], Спис ).

собрать( [ ], Закрытый, Закрытый).

% Кандидатов в Закрытый больше нет

собрать( [X |Открытый], Закрытый, Спис) :-

принадлежит( Х | Закрытый), !,

% Х уже собран ?

собрaть( Открытый,Закрытый, Спис).

% Отказаться от Х

собрать( [X |Открытый], Закрытый, Спис) :-

соседи( X, Соседи),

% Найти соседей Х

конк( Соседи, Открытый, Открытый1),

% Поместить их в Открытый

собрать( Открытый1, [X | Закрытый], Спис).

% Собрать остальные

Отношение конк - как всегда - отношениеконкатенации списков.

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

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

конк( [ ], 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, е]

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

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

[а, b, с]

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

L1 = [a, b, c, d, e]

L2 = [d, e]

Подобная пара списков, записанная длякраткости как L1-L2, представляет собой "разность" между L1 и L2. Этопредставление работает только при том условии,что L2 - "конечный участок" списка L1. Заметим,что один и тот же список может быть представленнесколькими "разностными парами". Поэтомусписок [а, b, с] можно представить как

[а, b, с]-[ ]

или

[a, b, c, d, e]-[d, e]

или

[a, b, c, d, e | T]-[d, e | T]

или

[а, b, с | Т]-Т

где Т - произвольный список, и т.п. Пустой списокпредставляется любой парой L-L.

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

конкат( A1-Z1, Z1-Z2, A1-Z2).

Давайте используем конкат дляконкатенации двух списков: списка [а, b, с],представленного парой [а, b, с | Т1]-Т1, исписка [d, e], представленного парой [d,e | Т2]-Т2 :

?- конкат( [а, b, с |Т1]-T1, [d, е | Т2]-Т2, L ).

Оказывается, что для выполнения конкатенациидостаточно простого сопоставления этой цели спредложением конкат. Результатсопоставления:

T1 = [d, e | Т2]

L = [a, b, c, d, e | T2]-T2

Рис. 8. 4. Отношения впоследовательности Фибоначчи."Конфигурация" изображается

здесь в виде большого круга и определяетсятремя параметрами: индексом М и двумя

последовательными числами f( M-1) и f( М).

Упражнения

8. 1. Все показанные нижепроцедуры подсп1, подсп2 и подсп3реализуют отношение взятия подсписка. Отношение подсп1имеет в значительной мере процедурноеопределение, тогда как подсп2 и подсп3написаны в декларативном стиле. Изучитеповедение этих процедур на примерах несколькихсписков, обращая внимание на эффективностьработы. Две из них ведут себя одинаково и имеютодинаковую эффективность. Какие? Почемуоставшаяся процедура менее эффективна?

подсп1( Спис,Подспис) :-

начало( Спис, Подспис).

подсп1( [ _ | Хвост],Подспис) :-

% Подспис - подсписок хвоста

подсп1( Хвост, Подспис).

начало( _, [ ]).

начало( [X | Спис1], [X |Спис2] ) :-

начало( Спис1, Спис2).

подсп2( Спис,Подспис) :-

конк( Спис1, Спис2, Спис),

конк( Спис3, Подспис, Cпис1).

подсп3( Спис,Подспис) :-

конк( Спис1, Спис2, Спис),

конк( Подспис, _, Спис2).

8. 2. Определите отношение

добавить_в_конец(Список, Элемент, НовыйСписок)

добавляющее Элемент в конец списка Список;результат - НовыйСписок. Оба спискапредставляйте разностными парами.

Посмотреть ответ

8. 3. Определите отношение

обратить( Список,ОбращенныйСписок)

где оба списка представлены разностнымипарами.

Посмотреть ответ

8. 4. Перепищите процедуру собратьиз разд. 8.5.2, используя разностное представлениесписков, чтобы конкатенация выполняласьэффективнее.

Резюме

Для оценки качества программы существует несколько критериев:

правильность

эффективность

простота, читабельность

удобство модификации

документированность

Принцип пошаговой детализации - хороший способ организации процесса разработки программ. Пошаговая детализация применима к отношениям, алгоритмам и структурам данных.

Следующие методы часто помогают находить идеи для совершенствования программ на Прологе:

Применение рекурсии: выявить граничные и общие случаи рекурсивного определения.

Обобщение: рассмотреть такую более общую задачу, которую проще решить, чем исходную.

Использование рисунков: графическое представление помогает в выявлении важных отношений.

Полезно следовать некоторым стилистическим соглашениям для уменьшения опасности внесения ошибок в программы и создания программ, легких для чтения, отладки и модификации.

В пролог-системах обычно имеются средства отладки. Наиболее полезными являются средства трассировки программ.

Существует много способов повышения эффективности программы. Наиболее простые способы включают в себя:

изменение порядка целей и предложений

управляемый перебор при помощи введения отсечений

запоминание (с помощью assert) решений, которые иначе пришлось бы перевычислять

Более тонкие и радикальные методы связаны сулучшением алгоритмов (особенно, в частиповышения эффективности перебора) и ссовершенствованием структур данных.

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

Оглавление