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

[Ruslan Zakirov]

2010/1/9 Alex Kapranoff <kapranoff на gmail.com>:
> Всем привет!

Привет.

> Вроде простая совсем задачка: https://www.spoj.pl/problems/SUMITR/
>
> А поди ж ты, на самом плохом тесткейсе в 2 секунды на довольно мощной
> машине уложить не могу :(

Похоже и не получиться без улучшения производительности perl.

> На Си хватает и половины секунды. В комментах пишут, что и Питон
> справляется. Хочет кто-нибудь поиграться?

Куда играться-то? Лучше алгоритма чем Дейкстры не придумаешь для это задачки.

> Моё решение (до сжатия кода, понятно): http://ideone.com/alWtxXxt

У меня есть прямое, которое по ходу считает, а потом в нижнем ряду
находит максимум. Разница не значительная.

В итоге в твоем решении тратиться:
3 сек с копейками на split
7 сек на ~5000000 сравнений и суммирований
1.2 сек на вывод результата

Вот такая математика. Пока 7 секунд не превратятся в 1, о каком-то
приближении к топу и быть не может.

-- 
Best regards, Ruslan.