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

[Alex Kapranoff]

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, о каком-то
> приближении к топу и быть не может.