Доделал свой итеративный вариант, он проходит без увеличения памяти и
стеков до N=100000 (сто тысяч) за 1м40сек (100 сек).
10000 (десять тысяч) проходит за 1 сек.
// Здесь строка eS еще не проверена на отсутствие повтора в ее начале
EX1 sN eS : {
// Goal!
0 e = eS;
// eS is unacceptable
sN vA vA e = <Next sN eS>; // tail recursion, eS is not empty (otherwise
previous sentence works)
// eS is acceptable
sN e = <EX1 <SUB sN 1> 'a' eS>;
};
Next {
sN = (); // Global Fail
sN sX eS = {
/* Choose next symbol after sX if any */
'abc' : e sX sY e = <EX1 sN sY eS>;
/* No next symbol -> go back */
= <Next <ADD sN 1> eS>;
};
};
Это по структуре похоже на то, что прислал Василий. Но наверно, более
экономно.
Здесь нет откатов, простой цикл, состояние - вся текущая строка.
пн, 25 февр. 2019 г. в 19:48, swi_AT_cnshb.ru <refal@botik.ru>:
> Уважаемые господа!
> Я тоже дочитал...
> А тест Аркадия меня подвиг его повторить.
> У меня на рефале/2 получилась следующая программа:
> a =/0/k/P/k/EX//10000/..
> EX /0/eS=eS
> sN eS=k/EX1/('abc'sN)eS.
> EX1 (sa eb sN)eS=k/EXc/(eb sN)sa eS.
> (sN)saeS=k/EX1p/k/P1/sN.sa('abc')eS.
> EX1p sN sa(e1 sa eb)eS=k/EX1/(eb sN)eS.
> EXc w0 sa eA sa eA ee=k/EX1/w0 eA sa eA ee.
> (eb sN)eR=k/EX/k/M1/sN.eR.
>
> я старался использовать идентификаторы переменных как на рефале-6...
>
> Кстати, ех 10000 у меня прошло, и менее чем за минуту (разница во времени
> файла результата "компиляции" и результата) см. приложенный файл.
>
> 25.02.2019, 16:51, "Arkady Klimov arkady.klimov_AT_gmail.com" <
> refal@botik.ru>:
>
> Я не только дочитал, наконец, но и внес свои правки-дополнения (в раздел
> по Рефал-6, и чуток по Рефал Плюс), поместив этот замечательный текст в
> doc-файл, который можно взять по ссылке:
>
> https://www.dropbox.com/s/eq4yv9g7atu59d7/CompareRefals.doc?dl=0
>
> Я подумал, что хорошо бы моему примеру последовали и "держатели" других
> диалектов.
> Александр, поручаю Вам быть "хозяином" этого файла, можете забрать его и
> выложить где-то от себя. Мои добавки, помеченные цветом и префиксом "АрК",
> можете в своем стиле адоптировать.
> Будет замечательно, если Вы сможете сделать из этого публикацию в
> ближайшее время. Призываю всех, кто чем может (правками, замечаниями и тп),
> этому посодействовать.
> ***
> Я по ходу решил еще раз почитать документацию-руководство по Рефалу Плюс.
> У меня сложное отношение к нему, то есть он как-то всегда был сложен для
> меня. Как я сейчас понял, возможно это из-за специфического описания
> синтаксиса, содержащего понятия "тропы" и "хвосты". Они очень похожи, и я
> всегда их путал и не мог привыкнуть различать. Для этого было бы полезно
> видеть их семантическое различие, чем я не владею. А описание языка
> такового не предлагает. Остается только "зазубривать" формальные
> особенности, напрягая свою внутреннюю "нейросеть". Хорошо бы те, кто
> владеют семантическим пониманием хвостов и троп Рефала Плюс, если таковое
> существует, его как-то эксплицировали.
> ***
> В руководстве мне встретился интересный пример - задача "о цепочках" (из
> Вирта), раздел 1.10. Надо породить строку из трех знаков (a, b, c), чтобы в
> ней не было одинаковых смежных подстрок.
> Решение довольно мутное, тем более оно дважды использует $Iter, который я
> не люблю (вероятно, авторы, хотели именно его иллюстрировать этим
> примером). И мне захотелось переписать его в более "чистых" терминах. И вот
> что у меня получилось:
> ----------------------------------------------------------------------------------------------------------
> файл abc.ref
> // <EX sN eS> - расширить строку eS влево sN знаками a,b,c,
> // не допуская повторов смежных подстрок
> EX {
> 0 eS = eS;
> sN eS , 'abc' : e sX e , sX eS : eR : # vA vA e, <EX <SUB sN 1> eR>;
> };
>
> ------------------------------------------------------------------------------------------------------------
> Это рефал-6, но думаю, можно по аналогии и на Плюсе написать (может даже и
> так пройдет).
> Функция EX откатная, при успехе выдает продолженную строку, иначе откат.
> Образец e sX e перебирает три варианта продолжения, образец vA vA e под
> отрицанием проверяет, что выражение не начинается с двух одинаковых
> непустых подстрок, дальше идет рекурсивный вызов, все через запятую
> прозрачно для откатов.
> Назвал функцию заглавными покороче, чтобы в интерактивной моде вызывать:
> d:\ref6\TEST>d:\ref6\rix.exe i+abc+*ask -S1000000 -T1000000 -H1000000
> #>ex 5
> 'acaba'
> #>ex 10
> 'bcacbacaba'
> #>ex 100
>
> 'cacbacabacbabcabacabcbabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbacabacbabcacbacaba'
> #>ex 1000
>
> 'acbabcacbacabacbabcbacbcabacbabcacbacabacbabcabacabcbabcabacbabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcbabcacbacabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacabacbcacbacabacbabcacbacabacbcacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacabacbcacbacabacbabcacbacabacbcacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbacabacbabcabacabcbabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbacabacbabcacbacaba'
> #>ex 10000
> EVAL: *** SYSTEM: Reference counter overflow
> The referenced object is: *EX
> EVAL: Act Vf Fre Run [n]Step [n]Trc Evl Chg Kil New Inf M W D H cLr Quit>
>
> Пришлось задать большой стек S и таблицу элементов Т (по 1000000
> элементов, по 16 и 8 байтов соответственно), и 1 ГБ (H Kb) общей памяти,
> иначе стеки быстро переполнялись. Здесь на каждый следующий элемент строки
> вводится уровень в стеке из-за возможности откатов. Но все равно на
> аргументе 10000 сломалось - по переполнению счетчика ссылок на объект *EX
> (символ функции). По-видимому, каждый уровень стека содержал несколько
> экземпляров ссылок, а всего в реализации счетчик ссылок не может превысить
> 2^15.
>
> Хороший тест получился. Показал некоторые пределы реализации.
>
> Решение на Рефал Плюс из руководства тоже жадно до стека. Интересно, какие
> там пределы?
>
> На получение строки наибольшей длины (около 6500) ушло чуть меньше
> секунды. По-видимому, на последней версии Рефала Плюс будет быстрее: либо
> из-за не копирований eS и eR (благодаря "дыркам"), либо из-за более
> оптимального отождествления vA vA e: уравнения на длинах должны ограничить
> удлинение переменной vA только до половины длины аргумента, а в Рефале-6
> она тупо продолжает удлиняться до конца аргумента.
>
> Надеюсь, было не скучно.
> Аркадий
>
>
--
_______________
*С уважением, *
*Аркадий Климов,*
*с.н.с. ИППМ РАН,*
*+7(499)135-32-95*
*+7(916)072-81-48*
