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

[Alexander V Alekseev]

On Sat, 9 Jan 2010, Alex Kapranoff wrote:

> Всем привет!
>
> Вроде простая совсем задачка: https://www.spoj.pl/problems/SUMITR/
>
> А поди ж ты, на самом плохом тесткейсе в 2 секунды на довольно мощной
> машине уложить не могу :(
>
> На Си хватает и половины секунды. В комментах пишут, что и Питон
> справляется. Хочет кто-нибудь поиграться?
>
> Моё решение (до сжатия кода, понятно): http://ideone.com/alWtxXxt
> Плохой тесткейс: http://dl.dropbox.com/u/360558/input_big.txt.gz
> (распакуется в 14 мег)
$cat input_big.txt | LC_ALL=C time perl -le 'while(<STDIN>){ chomp; split(" ",$_);}'
1.29user 0.00system 0:01.36elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+464minor)pagefaults 0swaps

У меня не самая мощная машина, но на вычисления остаётся ~ 0.7 сек.

С другой стороны:
$cat input_big.txt | time perl -le 'sysread(STDIN,$dd, 100_000_000); foreach (split("\n",$dd)){ split(" ", $_);}; print length($dd);'
14853005
1.59user 0.04system 0:01.67elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+8733minor)pagefaults 0swaps

Т.е. ещё хуже.

Для решения input_big.txt нужно выполнить как минимум
1000*99*(99+1)/2 =  4950000 сложений.

$time perl -le 'for(1 .. 4950000) { $a = $b + 1;}'
1.19user 0.00system 0:01.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+480minor)pagefaults 0swaps

Подозреваю, что на моём mobile core2 без шансов.