Subject: Re: Who has a fish?
From: Sergei M. Abramov (abram@botik.ru)
Date: Mon Apr 08 2002 - 16:56:50 MSD
День добрый, всем!
> По адресу http://www.refal.net/~korlukov/pearls/ryba/
> (имеется выход со страницы http://www.refal.net/~korlukov/pearls/ )
> размещен еще один пример применения суперкомпилятора Scp4.
Отличная жемчужина...
> Суперкомпилируемая программа состоит из 20 вложенных фильтров -
> 15 фильтров соответствуют 15 подсказкам в условии задачи,
> оставшиеся 5 фильтров проверяют наличие каждого объекта из
> условия по одному разу.
...
> Предлагается программа, при суперкомпиляции которай за 1 час
> 30 минут получается решение задачи.
Интересно узнать, как зависит время суперкомпиляции программы при изменении
порядка фильтров (я имею в виду всех двадцати: 15+5). Например, на
прямо-противоположный порядок (вхутри F, снаружи Z)...
Ведь с логической точки зрения вложенные фильтры это просто "И"? То есть
операция вроде как коммутативная?
Но мне кажется, что при перемене порядка вложения будет некий эффект со
временем счета...
> ... перебору 525 случаев. Это число равно 298023223876953125,
> примерно 1018 , т.е. миллиард миллиардов. Поэтому очень
> затруднительно измерить время
Удачи
Сергей
PS. Интересно эту задачу сделать на последних X-URA-х для XSG.
Из общих соображений там можно использовать справедливую (fair) операцию AND
(mgu-based) для 20 фильтров. То есть (кажется) там можно получить 20
невложенных предикатов и независимость от порядка.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD