Subject: Re: Who has a fish?
From: korlyukov (korlyukov@grsu.grodno.by)
Date: Mon Apr 08 2002 - 22:10:15 MSD
Сергей, спасибо.
> Интересно узнать, как зависит время суперкомпиляции программы при
изменении
> порядка фильтров (я имею в виду всех двадцати: 15+5). Например, на
> прямо-противоположный порядок (вхутри F, снаружи Z)...
При работе над этим примером я пробовал менять местами Z и F - из двух
вариантов я выбрал более лучший.
Был у меня и соблазн менять порядок внутри Z. Я испугался обвинений в том,
что буду делать подсказки суперкомпилятору.
Сейчас попробовал изменить порядок внутри Z - результат оказался совершенно
неожиданным для меня. Время суперкомпиляции снизилось с полутора часов до 5
мин 35 секунд !!!
Привожу тот порядок, который был у меня. Почему я выбрал именно такой
порядок? Из соображений очевидности, наверное. Сначала расположил те
подсказки, которые несут больше информации. Человек именно так и поступает.
9. Норвежец живет в первом доме.
7. Жилец из среднего дома пьет молоко.
1. Англичанин живет в красном доме.
2. Швед держит собаку.
3. Датчанин пьет чай.
5. Жилец зеленого дома пьет кофе.
6. Человек, который курит Pall Mall, держит птицу.
8. Жилец из желтого дома курит Dunhill.
14. Немец курит Rothmans.
12. Курильщик сигарет Winfield пьет пиво.
10. Курильщик Marlboro живет около того, кто держит кошку.
11. Человек, который держит лошадь, живет около того, кто курит Dunhill.
13. Норвежец живет около голубого дома.
15. Курильщик Marlboro живет по соседству с человеком, который пьет воду.
4. Зеленый дом стоит слева от белого.
Александр
----- Original Message -----
From: "Sergei M. Abramov" <abram@botik.ru>
To: "korlyukov" <korlyukov@grsu.grodno.by>; "refal" <refal@botik.ru>
Cc: "Andrei P. Nemytykh" <nemytykh@whu.edu.cn>;
<Aleksey_Korlukov@atlantm.com>
Sent: Monday, 08 April 2002 15:56
Subject: Re: Who has a fish?
> День добрый, всем!
>
> > По адресу 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