On Thu, Feb 28, 2019 at 10:03 AM Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:
> Мда, как я понял, код для eR : vA vA e далек от оптимальности.
> На каждое очередное удлинение первой vA:
> 1. Проверяем, что не дошли до конца eR.
> 2. Вычисляем длину vA (len6) и длину дополнения vA до eR (len5).
> 3. Проверяем, что не (len5 < len6) -- этим обеспечивается удлинение до
> половины
> 4. Вычисляем разницу len5-len6 (это будет длина остатка e)
> 5. Вызываем сравнение vA и ее дополнения до eR -- тут я не понял, надо
> чтобы eV было не *равно *дополнению, а было *началом *дополнения, а где
> это сказано?
>
Expr1.eq(Expr2, offset) проверяет, что Expr1 является подвыражением Expr2,
начиная с offset.
> В общем, довольно много всего. Поэтому не удивительно, что только
> чуть-чуть обгоняет рефал-6, в котором удлинение происходит всегда до конца
> eR (даже без оптимизации удлинения до старого символа).
> А надо бы: вне цикла разделить длину eR пополам, перед вызовом функции
> сравнения цепочек быстро сравнить первые термы и не вычислять прежде
> времени длину остатка e.
>
Действительно, зря вычисляется длина остатка, и зря он потом заводится. Это
должна была убрать элиминация неиспользуемых переменных, но она так и не
была написана (отчасти потому, что на самом деле во многих случаях
компилятор C++ вполне успешно справляется с этим сам).
Каждый раз проверять, что не дошли до конца eR тоже не надо, конечно.
Остальное всё по сути -- длина фактически известна (это уж компилятор С++
пусть думает, как лучше счётчик инкрементировать), сравнение длин нужно
(ничем не хуже, чем сравнение с упополамленной длиной).
Однако, для интереса, закомментировал лишнее. Получилось на 10к (по 10
запусков на каждый):
Изначально:
Mean Std.Dev. Min Median Max
0.481 0.004 0.478 0.481 0.491
Подчищенное:
Mean Std.Dev. Min Median Max
0.475 0.003 0.471 0.475 0.483
Антон
Аркадий
>
> чт, 28 февр. 2019 г. в 16:30, Anton Orlov orlovan_AT_gmail.com <
> refal@botik.ru>:
>
>> On Thu, Feb 28, 2019 at 8:18 AM Arkady Klimov arkady.klimov_AT_gmail.com
>> <refal@botik.ru> wrote:
>>
>>> Кстати, Антон, а правильно я понимаю, что в нынешней реализации Р+ при
>>> отождествлении образца
>>> vA vA e
>>> первая vA удлиняется только до половины длины аргумента?
>>>
>>
>> Да, до половины.
>> В приложении выходной код на С++ (промежуточный файл, который дальше
>> компилятору C++ отдаётся) -- в рантайме и компиляторе специально были
>> предприняты усилия, чтобы этот код был читаем.
>>
>> Антон
>>
>> В противном случае (если удлиняется до конца аргумента) разница по
>>> эффективности между удлинением и Iter еще вдвое больше.
>>>
>>> чт, 28 февр. 2019 г. в 15:54, Arkady Klimov <arkady.kli...@gmail.com>:
>>>
>>>> Там есть и небольшое содержательное отличие, хотя оно зависит от того,
>>>> с какой стороны идет сравнение выражений eU : eV.
>>>> Если, как естественно предположить, слева, то это и создает некоторую
>>>> разницу. Наращиваем направо, удлиняем справа налево, а сравниваем слева
>>>> направо. Вопрос теперь в том, не будет ли при этом среднее число совпадений
>>>> на каждом сравнении больше, чем если с другой стороны начинать сравнение.
>>>> Но это надо отдельно изучать.
>>>> Но конечно, основная причина, видимо, в накладных на вызовы. Это просто
>>>> показывает, что итерации через удлинения сами по себе гораздо эффективнее,
>>>> чем аналогичные итерации через $Iter со всеми сопутствующими
>>>> дополнительными вызовами.
>>>> Аркадий
>>>>
>>>> чт, 28 февр. 2019 г. в 02:34, Anton Orlov orlovan_AT_gmail.com <
>>>> refal@botik.ru>:
>>>>
>>>>>
>>>>>
>>>>> On Tue, Feb 26, 2019 at 5:41 AM Yuri Klimov yuri_AT_klimov.net <
>>>>> refal@botik.ru> wrote:
>>>>>
>>>>>> Добрый день!
>>>>>>
>>>>>> Пример Аркадия на Рефал+:
>>>>>>
>>>>>> $func? EX sN eS = eS;
>>>>>> EX \{
>>>>>> 0 eS = eS;
>>>>>> sN eS , 'abc' : e sX e , sX eS :: eR, # \{ eR : vA vA e; }, <EX
>>>>>> <Sub sN 1> eR>;
>>>>>> };
>>>>>>
>>>>>> Я ошибся. По умолчанию в компиляторе были выключены оптимизации и
>>>>>> включен режим отладки. Теперь время около 0.62 секунд.
>>>>>>
>>>>>> Пример с двумя iter из документации в приложении. Требует heap'а чуть
>>>>>> поменьше (1ГБ против 2ГБ). Считает 10.5 секунд.
>>>>>>
>>>>>
>>>>> Это, кстати, очень интересно, потому что пример с двумя $iter делает
>>>>> по сути всё то же самое (только выражение растит в другую сторону).
>>>>> И такая разница во времени получается из-за накладных расходов на
>>>>> вызовы функций (самой Unacceptable и селекторов -- Middle, Right). Хотя
>>>>> они
>>>>> и не копируют выражения, но надо поместить аргументы на стек, вызвать,
>>>>> убрать со стека, привести длинный Int к обычному (в аргументе) и т.п. --
>>>>> всё это действия, которые отсутствуют при сопоставлении eR : vA vA e.
>>>>>
>>>>> Антон
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> Второй пример Аркадия на Рефал+ считает без heap'а за около 0.76
>>>>>> секунд:
>>>>>>
>>>>>> $func EX1 sN eS = eS;
>>>>>> EX1 sN eS, sN eS : {
>>>>>> sN vA vA e = <Next sN eS>;
>>>>>> 0 e = eS;
>>>>>> sN e = <EX1 <Sub sN 1> 'a' eS>;
>>>>>> };
>>>>>>
>>>>>> $func Next sN eS = eS;
>>>>>> Next {
>>>>>> sN = ();
>>>>>> sN sX eS = {
>>>>>> 'abc' : e sX sY e = <EX1 sN sY eS>;
>>>>>> = <Next <Add sN 1> eS>;
>>>>>> };
>>>>>> };
>>>>>>
>>>>>>
>>>>>> С уважением,
>>>>>> Юрий Климов
>>>>>>
>>>>>> P.S. Во втором примере ошибка:
>>>>>>
>>>>>>> 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)
>>>>>>> ...
>>>>>>
>>>>>> Надо эти два случая переставить местами, а то иначе последних (самый
>>>>>> левый в строке) символ не проверяется на повторы.
>>>>>>
>>>>>> On Tue, 26 Feb 2019 at 09:29, Sergei M. Abramov abram_AT_botik.ru <
>>>>>> refal@botik.ru> wrote:
>>>>>>
>>>>>>> День добрый,
>>>>>>>
>>>>>>> > Запустил исходный пример Аркадия на Рефале+ (с компиляцией C++).
>>>>>>> > Heap пришлось увеличить до 2GB. Время - 2.05 секунды.
>>>>>>>
>>>>>>> Юра, сделайте с двумя $iter-ами, пожалуйста. Хочется и на текст
>>>>>>> полюбоваться, и на прогон.
>>>>>>>
>>>>>>> Под руками системы нет, а в сухую (без воды в бассейне) и облажаться
>>>>>>> могу...
>>>>>>>
>>>>>>> Всего доброго,
>>>>>>>
>>>>>>> Сергей Абрамов
>>>>>>>
>>>>>>>
>>>>
>>>> --
>>>> _______________
>>>> *С уважением, *
>>>> *Аркадий Климов,*
>>>> *с.н.с. ИППМ РАН,*
>>>> *+7(499)135-32-95*
>>>> *+7(916)072-81-48*
>>>>
>>>
>>>
>>> --
>>> _______________
>>> *С уважением, *
>>> *Аркадий Климов,*
>>> *с.н.с. ИППМ РАН,*
>>> *+7(499)135-32-95*
>>> *+7(916)072-81-48*
>>>
>>
>
> --
> _______________
> *С уважением, *
> *Аркадий Климов,*
> *с.н.с. ИППМ РАН,*
> *+7(499)135-32-95*
> *+7(916)072-81-48*
>
