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

[Ruslan Zakirov]

Последний вариант. Отдельное префиксное индексирование чуть быстрее.

Попробовал 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);
            ++$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.