Subject: Re: Как следует компилировать рефальску операцию отождествлени
From: Arkady Klimov (klark@bagirra.net)
Date: Sat Dec 09 2000 - 15:27:38 MSK
----- Original Message -----
From: Sergei M. Abramov (at home) <abram@botik.ru>
To: Arkady Klimov <klark@bagirra.net>; <refal@botik.ru>; Andrey Slepuhin <pooh@msu.ru>; Anton Yu. Orlov <orlov@mccme.ru>
Sent: Friday, December 08, 2000 6:26 PM
Subject: Re: Как следует компилировать рефальскую операцию отождествления
| Алик, привет!
|
| Извини, что долко молчал--замотался!
|
| -----Original Message-----
| From: Arkady Klimov <klark@bagirra.net>
| Date: 5 декабря 2000 г. 22:36
| Subject: Re: Как следует компилировать рефальскую операцию отождествления
|
|
| >Спасибо за инициативу и интересные материалы....
|
| >Все очень интересно.
|
| Спасибо на добром слове!
|
| >Для Р+ и вообще отображение в массивное представление
| >это то, что надо.
|
| Кажется--да.
|
| >Но в первом письме ты писал, что эти методы будут
| >также интересны для реализаторов Р-5 и т.п.,
| >то есть рефалов на списковом представлении.
|
| Да.
|
| >У меня есть в этом сомнения, попробуй их развеять.
| >Ты справедливо замечаешь, что сложность операций
| >может быть (и будет для списков) O(L). Но дальше
| >ты писал, что алгоритм от этого не зависит.
| >Согласен, алгоритм не зависит, но сложность его
| >зависит и возможно радикально.
|
| Более точно, что я ХОТЕЛ сказать (но возможно мне это НЕ ОЧЕНЬ удалось) это то,
| что ПОРА стать ревизионистами, пора навести ревизию, пора еще раз подумать.
|
| По крайней мере для случая квази-закрытых переменных:
|
| e.Src : e1 A e1 B e1 C e1 D e1
|
| предложенный ревизионизм эффективен для любого представления (списковое,
| массивное): он работает как О(len_Src), вместо классического О(len_Src^4).
|
АРК:
Понятно, правда классический имеет здесь сложность О(len_Src^2) - не зависит от числа
добавочных переменных, которые здесь все повторные.
| Для меня это достаточный аргумент чтобы всех ПРИЗВАТЬ к попытке ревизионизма
| (ВСЕХ:
| остроконечников и тупоконечников,
| списочников и массивщиков,
| врезанных и подвешанных,
| со счетчиками и без).
|
| Думать надо всем. Потом разбираться, в каких случаях какие методы лучше/хуже
| для каких представлений.
|
| Еще раз: лично для меня достаточно демонстрации ОДНОГО ранее прозеванного
| случая, чтобы не побояться еще раз просмотреть (не побояться сделать ревизию).
|
| > ... Есть только опасение в том, что
| >значительная часть кода в компиляторе
| >и интелекта при его создании будут
| >потрачены как бы зря, поскольку в
| >практических программах не будут
| >востребованы ...
|
| Ну да, ну да... Можно сказать (даже доказать статистической обработкай архива
| всех в мире рефал-программ), что образцов вида "e.Src : e1 A e1 B e1 C e1 D e1"
| нормальные люди ме пишут...
|
| Ну да, до сих пор не писали (может быть). Но придет один новый юзер, напишет и
| ведь стыдно будет за эффективность.
Да, я тут с удовольствием соглашусь. Именно этот мотив мы всегда используем
в пропаганде суперкомпиляции.
|
| >Рассмотрим пример такого образца (из функции доступа к копилке):
| >
| >(e.name) (e.1 (e.name '=' e.value) e2)
| >
| >При существующей реализации его сложность - это объем символов из содержимого
| >правого списка, которые надо просмотреть при поиске.
|
| Ну... все-таки, я бы сказал, что О(L_name x L_storage). И это не зависит от
| реализации...
|
| >Когда сравнение неудачное, это обычно
| >1-2 символа на одно имя.
|
| ;-)))) Посволь мне не согласиться и сказать, так "когда сравнение неудачное, это
| обычно О(L_name/2)==О(L_name) символа на одно имя.
|
| > ... То есть время будет грубо пропорционально
| >количеству имен.
АРК:
Я имел в виду случай, когда имена и обращения по ним "хорошо перемешаны". Тогда даже при двухбуквенном алфавите средняя глубина
(=среднее время) просмотра имени при сравнеиии будет 2 (1 с вероятностью 1/2, 2 с вероятностью 1/4 , 3 с вероятностью 1/8 и т.д.)
|
| Ну уж нет, я бы сказал, что О(L_name x L_storage)
|
| >Если же перед сравнением мы будет сначала вычислять длину,
| >тратя O(L), то время поиска резко увеличится в разы - пропорционально средней
| >длине имени.
|
| Время увеличится в О(1), сохранив порядок О(L_name x L_storage) ;-))
|
| >Но, повторяю, мое сомнение касается только
| >применимости этих методов к списковой
| >реализации.
|
| Принято. Бесспорно.
|
| А мои призывы были такие: лично мне одного примера достаточно для того, чтобы
| призвать ЗАДУМАТЬСЯ.
А мне показалось, что ты утверждал, что новый метод является равномерно-неухудшающим в том числе и при списковой реализации. И
только с этим я стал спорить.
|
| А после этого применять или не применять--да черт с ним, в конце концов это дело
| вкуса (и лени) реализатора.
|
| В конце концов, мое любимое про программиста: "Сынок, ради Бога ничего не меняй!
| Пусть все так и остается!"
|
| Но в главном ты прав:
|
| > ... Но это я так написал, чтобы иметь в виду,
| >на самом деле надо продолжать в том же духе,
| >и смотреть, что получается. А там видно
| >будет.
|
| Это точно. Если не пробовать, то видно не будет ;-)))
|
| > ... Короче, я бы призывал ... вести ее разработку
| >с прицелом на векторное представление, не оглядываясь
| >на списки.
|
| Так и делаем.
|
| Разок, походя, призвали списочников оглянуться (на всякий случай) на эти
| методы--вдруг понравится (по крайней мере в одном-то случае они эффективны ;-)?
| Или просто из гуманистических побуждений захочется каплю свежего взгляда и
| интеллекта потратить "на чужом поле", пролить на чужую мельницу...
|
| Что же касается идеи "поддержка длины в списочном представлении":
|
| > ... И тут мы возвращаемся к тому с чего
| >начали - практической невозможности
| >организовать вычисление и хранение
| >длин списков с приемлемой для
| >режима интерпретации сложностью.
|
| Ты знаешь, чисто интуитивно я с тобою не соглашусь. Мне все-таки >>кажется<<,
| что
| ==> в любой РАЗУМНОЙ списковой реализации Рефала за РАЗУМНЫЕ затраты (не
| зависящие от длин);
| ==> МОЖНО сделать ДЕШЕВОЕ отслеживание длин
| -- ВСЕХ ПОДВЕШЕННЫХ скобок,
| -- всех АРГУМЕНТОВ в К-термах (вызов функции--те же подвешенные
| скобки, в некотором роде).
|
| Но я не готов тратить свое (и твое) время на проверку (опровержение) этого моего
| интуитивного утверждения. Окончательно это доказывается только завершенной
| отлаженной реализацией и это дело реализатора из лагеря списочников (не я).
Да, мне тоже кажется, что принципиальная возможность этого существует. Но много технических сложностей.
|
| >Короче, я бы призывал не мудрствовать
| >по поводу "единой для всех" схемы компиляции,
| >а просто вести ее разработку с прицелом
| >на векторное представление, не оглядываясь на списки.
|
| Согласен с твоими призывами. Не оглядоваемся (вот уже .... лет).
|
| >Потом интересно будет посмотреть,
| >нельзя ли сделать заметное упрощение
| >в арсенале приемов, при котором типичные
| >случаи практически не пострадали бы.
|
| Ты знаешь, кажется и так все настолько просто вышло. Пока кажется--проще
| некуда.
Возможно.
Успехов!
Аркадий.
|
| Удачи,
|
| доживем до реализации (не за горами, я надеюсь...)
|
| Сергей
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD