Да, 1.5%, не густо. В принципе, конечно, пусть дальше думает С++.
Но текущий вряд ли догадается чего-то вытащить из функции.
А в Р6 v-переменные еще на входе заменяются на t e, поэтому первые термы
отдельно сравниваются.
И поэтому накладные на подготовку цикла сравнения (vA vA e) уже не столь
значимы.
Правда, обратный образец (e vA vA) будет смертоубийством: удлинений справа
нет.
А у вас, наверно, равноценно, да?
Аркадий
чт, 28 февр. 2019 г. в 19:00, Anton Orlov orlovan_AT_gmail.com <
refal@botik.ru>:
> 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*
>>
>
--
_______________
*С уважением, *
*Аркадий Климов,*
*с.н.с. ИППМ РАН,*
*+7(499)135-32-95*
*+7(916)072-81-48*
