[Moscow.pm] Сложить 5000000 чисел

[Alex Kapranoff]

2010/1/11 Ruslan Zakirov <ruslan.zakirov на gmail.com>:
> Последний вариант. Отдельное префиксное индексирование чуть быстрее.

В нём ошибка, из-за которой всё работает на целых 25% быстрее, но неправильно :)

> Попробовал splice, но он медленнее
>
> undef $/; @file = split ' ', scalar <>;
>
> $res = '';
> for (1 .. shift(@file)) {
>    $rows = $file[$cur++];
>
>    @s = (0) x ($rows + 1);
>    for (0 .. $rows-1) {
>        $i = 0; $y = 0;
>        $cur += $_;
>
>        for ($cur .. $cur+$_) {
>            $x = $y;
>            $y = $s[$i];
>            $s[$i] = $file[$cur] + ($x > $y? $x : $y);

Вот тут должно было $file[$_]. Использование $cur реально всё
ускоряет. Это означает, что либо у нас оптимизатор умеет вычислять
неизменяющиеся выражения перед циклом, либо срабатывает эффект
процессорного кэша.

>            ++$i;
>        }
>    }
>
>    $m = 0;
>    $m < $_ and $m = $_ for @s;
>    $res .= $m;
>    $res .= "\n";
>
>    $cur += $rows;
> }
> print $res;
>
>
> 2010/1/10 Alex Kapranoff <kapranoff на gmail.com>:
>> 2010/1/10 Ruslan Zakirov <ruslan.zakirov на gmail.com>:
>>> 2010/1/9 Alex Kapranoff <kapranoff на gmail.com>:
>>>> Вроде простая совсем задачка: https://www.spoj.pl/problems/SUMITR/
>>>>
>>>> А поди ж ты, на самом плохом тесткейсе в 2 секунды на довольно мощной
>>>> машине уложить не могу :(
>>>
>>> Похоже и не получиться без улучшения производительности perl.
>>>
>>>> На Си хватает и половины секунды. В комментах пишут, что и Питон
>>>> справляется. Хочет кто-нибудь поиграться?
>>>
>>> Куда играться-то? Лучше алгоритма чем Дейкстры не придумаешь для это задачки.
>>
>> Базовый алгоритм остаётся, да, но всякие мелочи можно оптимизировать.
>> У меня простейший оператор присваивания во внутреннем цикле занимает
>> почти секунду :)
>>
>> Добрые перломонахи подсказали пару интересных идей:
>> http://www.perlmonks.com/?node_id=816485
>>
>> В частности, я тоже перешёл на твой вариант считать сверху вниз, а
>> потом вывести максимум, чем срезал пару присваиваний. Ещё важным
>> предложением оказалось считать сразу весь файл в плоский массив, а всю
>> двухмерность рассчитывать по ходу дела индексами.
>>
>> Вот текущий вариант: http://ideone.com/np0UUaTO
>>
>> На плохом тесткейсе у меня на машине вместо 6 секунд работает всего
>> 3.5 :) Проверку на spoj.pl, правда, всё равно не проходит.
>>
>>> У меня есть прямое, которое по ходу считает, а потом в нижнем ряду
>>> находит максимум. Разница не значительная.
>>>
>>> В итоге в твоем решении тратиться:
>>> 3 сек с копейками на split
>>> 7 сек на ~5000000 сравнений и суммирований
>>> 1.2 сек на вывод результата
>>
>> У меня, кстати, в профиле вывод вообще не виден. Проверь ещё разок..
>>
>>> Вот такая математика. Пока 7 секунд не превратятся в 1, о каком-то
>>> приближении к топу и быть не может.
>> --
>> Moscow.pm mailing list
>> moscow-pm на pm.org | http://moscow.pm.org
>>
>
>
>
> --
> Best regards, Ruslan.
> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org
>