Доброй ночи!
Запустил исходный пример Аркадия на Рефале+ (с компиляцией C++). Heap
пришлось увеличить до 2GB. Время - 2.05 секунды.
С уважением,
Юрий Климов
P.S. Попутно обнаружил ошибочку в компиляторе. Сразу видно, что раньше
компилятор тестировался на машинах с меньше, чем 2ГБ памяти ;).
On Mon, 25 Feb 2019 at 20:53, Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:
> Доделал свой итеративный вариант, он проходит без увеличения памяти и
> стеков до 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*
>
