Subject: The plan of experiment
From: sasha korlyukov (korlyukov@mail.ru)
Date: Thu May 02 2002 - 11:00:04 MSD
План эксперимента
Три года назад, летом 1999 года в середине июля, в славном городе Переславле на
школе рефал-компании было устроено соревнование между различными реализациями
Рефала: Рефал-5, Рефал-Плюс и Рефал-6.
По-моему, назрела историческая необходимость включиться в это соревнование
суперкомпиляторам, как суперкомпилятору Рефала, так и суперкомпилятору Явы. И
одержать победу -:)
Я не помню точно всех деталей соревнования и его результаты, поэтому пишу это
письмо. Если будут неточности, то буду благодарен за любые уточнения, советы,
пожелания и комментарии.
Соревнование проходило на задаче "Выбор председателей".
Задача. В некотором множестве людей имеется несколько обществ. Требуется
выбрать в каждом обществе по одному председателю, так чтобы ни один человек не
занимал две должности председателей (в различных обществах).
Математическая постановка задачи. Имеются множества A1, A2, ... , An .
Требуется выбрать такие элементы a1, a2, ... , an , чтобы выполнялись условия:
1. Элемент ak принадлежит множеству Ak для любого k.
2. Все элементы a1, a2, ... , an различные.
Постановка задачи для соревнования. Алгоритм состоял в следующем. Дано
натуральное число n. Например, n = 5. По числу n строились n множеств:
{1, 2, 3, 4, 5}
{1, 2, 3, 4}
{1, 2, 3}
{1, 2}
{1}
Далее осуществлялся тривиальный перебор всех случаев (по-порядку), который
состоял из n! вариантов, при этом искомый вариант оказывался последним.
Ответ: {5, 4, 3, 2, 1}
Замечание. Если в качестве исходных данных задавать первое множество
{1, 2, 3, 4, 5},
то ответ {5, 4, 3, 2, 1} является инвертированием первоначального списка.
Поэтому все тогда понимали как задачу для суперкомпилятора задачу
суперкомпиляровать этот алгоритм и получить простую функцию инвертирования
списка.
Рассмотрим различные варианты применения суперкомпилятора в этой задаче.
Если специализация происходит по фиксированному числу n, то тогда произойдет
режим полной интерпретации, и построится конкретный ответ, например, {5, 4, 3,
2, 1}. Этот случай не представляет никакого интереса ни с какой точки зрения.
Время суперкомпиляции будет большим, а время исполнения остаточной программы -
ничтожно малым.
Если число n не будет задано суперкомпилятору, то тогда нет никакой
специализации. Алгоритм может несущественно ускориться. О победе в соревновании
мечтать не приходится. В общем, этот случай не является хорошей областью
применения суперкомпилятора (на настоящий момент времени).
По изложенным выше причинам не было никаких экспериментов по суперкомпиляции
задачи о выборе председателя.
Тем не менее, имеется шанс выиграть соревнование у всех рефалов сразу.
Я предлагаю суперкомпилировать функцию-предикат от двух аргументов
<F (e.1) (e.2) >
где
e.1 - известное число n (или список из n элементов, или все n множеств, при
теперешнем уровне развития суперкомпиляторов это все равно),
e.2 - неизвестный набор председателей.
Функция F устроена очень просто - она состоит из двух фильтров, каждый на одно
из условий
1. Элемент ak принадлежит множеству Ak для любого k.
2. Все элементы a1, a2, ... , an различные.
Специализация происходит по e.1 , остаточная программа будет функцией от
переменной e.2
Ожидаемая остаточная программа (при n=5) :
F {
5 4 3 2 1 = True;
e.1 = False;
}
В этом состоит эксперимент, который предлагается провести.
В чем именно состоит ожидаемая победа суперкомпилятора над реализациями
Рефалов? Будем сравнивать время суперкомпиляции предложенной функции-предиката
со временем исполнения Рефал-программ.
Я считаю, что возможная победа будет победой в честной борьбе.
Действительно, соревнования трехлетней давности проводились на условиях, когда
задано число n, и строился список ответа.
Суперкомпилятор будет в тех же условиях, получив число n он построит остаточную
программу, в которой будет иметься список ответа.
Если есть возражения или сомнения в последних моих утверждениях, то готов с
благодарностью их выслушать.
Все изложенное годится также и для суперкомпилятора Явы.
Александр
-----------------------------------------------
Примите участие в Секретном Турнире <Nike Scorpion K.O.>. Информация на
http://r.mail.ru/cln1938/www.nikefootball.com/sko/russia
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD