Профилирование ECLiPSe CLP?

Question

Я сделал две реализации, чтобы решить загадки Сикаку. Один использует Top,Left,Width и Height (TLWH) в качестве параметров для каждого прямоугольника, другой Top,Left,Bottom,Right (TLBR).

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

Есть ли способ профилировать решения ECLiPSe CLP?

В настоящее время я использую TkEclipse на Windows.

Answer 1

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

Основным фактором производительности CLP является размер и форма дерева поиска, которое, к счастью и к сожалению, зависит от многих факторов. К счастью, потому что это дает нам много возможностей влиять на дерево поиска. К сожалению, потому что это затрудняет прогнозирование производительности.

Второй фактор - сила распространения ограничений, которая несколько напрямую связана с тем, как была сформулирована модель. Например, одно "глобальное" ограничение (которое работает со многими переменными одновременно) обычно обеспечивает более сильное распространение, чем эквивалентная формулировка со многими меньшими ограничениями. Сила распространения в свою очередь влияет на размер дерева поиска.

Итак, чтобы выяснить, почему ваши две реализации ведут себя так по-разному, первым делом нужно сравнить их деревья поиска. Самый простой способ сделать это - посмотреть на количество возвратов, необходимое для поиска решения. Если вы используете предикат библиотеки search/6, вы можете получить счет через Options аргумент:

search(Xs, ..., ..., ..., ..., [backtrack(BT)]),
printf("Solution found after %d backtracks%n", [BT]),

Я использовал этот код Сикаку как свою модель TLBR, а модифицированную версию как модель TLWH. Для нахождения решения проблемы p(15,1) необходимо

TLBR: 0 backtracks
TLWH: 171 backtracks

Очевидно, что две программы делают очень разные вещи. В частности, модель TLBR выглядит намного "более узкой" и не требует особого поиска!

Чтобы выяснить, почему, я сравнил состояние вычислений непосредственно перед началом фазы поиска (я просто удалил вызов подпрограммы поиска и распечатал таблицу с ее частичными результатами - вы также можете использовать трассировщик и инструмент инспектора терминов, или другие инструменты визуализации). Оказывается, что в модели TLBR многие прямоугольники уже имеют свое окончательное размещение (т.е. их переменные координат уже созданы), в то время как в модели TLWH ни одна из них не имеет (их переменные все еще могут принимать много значений).

Более внимательный взгляд на подзадачу подсказывает причину. Рассмотрим только горизонтальные координаты, и предположим, что L - левый край, R - правый край, а W - ширина прямоугольника. Даны домены L и W, и прямоугольник должен покрывать точку 9. В модели TLBR это приводит к ограничениям:

?- L::6..9, W::1..4, R#=L+W-1, L#=<9, 9#=<R.
L = L{6..9}
W = W{1..4}
R = R{9..12}
There is 1 delayed goal.
Yes (0.00s cpu)

в то время как в модели TLWH мы должны написать последнее ограничение иначе, потому что у нас нет переменной R, доступной в этой точке:

?- L::6..9, W::1..4, Rimplicit#=L+W-1, L#=<9, 9#=<L+W-1.
L = L{6..9}
W = W{1..4}
Rimplicit = Rimplicit{6..12}
There are 2 delayed goals.
Yes (0.00s cpu)

Мы видим в модели TLWH, что область правого края, когда вычисляется из L+W-1, не отражает информацию о том, что она должна быть не менее 9. Мы потеряли некоторую силу распространения, не учитывая L+W-1 подвыражение, которое, как мне кажется, является основной причиной более слабого распространения.

Существует еще одна причина различия в деревьях поиска, заключающаяся в том, что у нас просто есть разные переменные для пометки: [L,R] в одном случае, [L,W] в другом. В частности, при использовании эвристики выбора переменных, чувствительной к домену, это может вызвать совсем другое поведение.