Чтобы понять, лучше ли iter чем рекурсия, я переделал последний вариант EX1
(хотя рекурсия там тоже не настоящая, хвостовая) через $iter. Антон или
Юра, сможете пропустить? А то я пока не умею этого.
Правда, вряд ли заметно ускорится, поскольку основное время здесь,
по-видимому, уходит все-таки на образец vA vA e.
// Result () indicates that such string does not exist
// Iter variable sP : { T - expression eS is ok; F - eS must be rebuild; U
- unknown }
$func EX2 s = e;
EX2 sN, T sN /* empty */ $Iter { sP eS : {
T e = U <Sub sN 1> 'a' eS;
U vA vA e = F sN eS;
U e = T sN eS;
F sa es, 'abc' : e sa sb e = U sN sb es;
F sc es = F <Add sN 1> es;
}} :: sP sN eS, sP sN eS : \{ T 0 e = eS; F s = (); };
Чтобы выразить все через единый цикл, пришлось ввести три состояния sP,
которые характеризуют имеющуюся информацию о допустимости текущей строки:
T - допустима, U - неизвестно, F - недопустима или все продолжения
оказались недопустимыми.
Конечно, нет уверенности, что написано правильно и без ошибок. Для
"отладки" я пропустил аналогичный вариант на р6, где вместо $iter
вспомогательная функция XX:
EX3 sN = <XX T sN /* empty */>;
XX {
T 0 eS = eS;
T sN eS = <XX U <SUB sN 1> 'a' eS>;
U sN vA vA eS = <XX F sN vA vA eS>;
U sN eS = <XX T sN eS>;
F sN sa es, 'abc' : e sa sb e = <XX U sN sb es>;
F sN sc es = <XX F <ADD sN 1> es>;
F sN = ();
};
Он работает примерно как и EX1 раньше. 10000 - 1 сек, 100000 - 94 сек на
свежезагруженном интерпретаторе. По мере тасования памяти скорость падает
до 2 раз.
Аркадий
пт, 1 мар. 2019 г. в 12:08, Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru>:
> День добрый, Антон, Юра!
>
> Я там как-то невнимательно следил.
>
> 1. Р+ с $iter должен быт лучше (не хуже) чем рекурсия. Но не сильно
> (хвостовая рекурсия мало уступает $iter).
>
> 2. Р+ с рекурсией не должен жрать стек (точнее, жрать и освобождать
> сразу, так как хвостовая).
>
> Так и есть? А если не так, то поясните, плз.
>
> Всего доброго,
>
> Сергей Абрамов
>
>
--
_______________
*С уважением, *
*Аркадий Климов,*
*с.н.с. ИППМ РАН,*
*+7(499)135-32-95*
*+7(916)072-81-48*
