[Moscow.pm] Сложить 5000000 чисел
Alex Kapranoff
kapranoff на gmail.com
Сб Янв 9 01:59:05 PST 2010
2010/1/9 Andrew Shitov <andy на shitov.ru>:
>> Плохой тесткейс: http://dl.dropbox.com/u/360558/input_big.txt.gz
> (распакуется в 14 мег)
>
> Пример какой-то странный. На нем нельзя убедиться, что программа
> работает правильно: все пути дают одинаковый результат, и
> пооптимизировать для случая со случайными данными не получится. Откуда
> этот файл?
Я его сгенерировал. Отладить алгоритм можно и на маленьких тестах.
> Моя вторая попытка (после прямолинейной первой) - начать считать не
> сверху, а снизу, отсеивая пути, которые на очередном шаге добавляют в
> результат меньше других.
Я тоже снизу считал, алгоритм очень похож на поиск пути в графе по
Дейкстре. Для каждого числа считается наибольший путь вниз если бы
треугольник начинался в этой точке. Получается O(n^2) и меньше вряд ли
можно.
> use v5.10;
> #use Data::Dumper;
> <>;@v=reverse map{[split/\s/]}<>;
> $s=$v[0];
> for(1..$#v){
> if($q==1){$q++;next}
> if($q==2){$q=0;$s=$v[$_];next}
> #say Dumper($s);
> $c=$v[$_];
> $n=$v[$_+1];
> if(@$c!=@$n){
> #say join',',@$c;
> $m=0;
> for(0..@$c-1){
> if($$s[$_]){$$s[$_]=$$c[$_]+($$s[$_]>$$s[$_+1]?$$s[$_]:$$s[$_+1]);$m=$$s[$_]if$$s[$_]>$m}
Вот из-за этого if-а неправильно обрабатывается вариант
1
1 1
1 1 1
1 1 1 2
http://ideone.com/JzdFSyes
> }
> pop@$s;
> @$s=map{$_!=$m?0:$_}@$s
> }else{
> push на r,$$c[0]+($$s[0]>$$s[1]?$$s[0]:$$s[1]);
> $q=1;
> #say '-'x20;
> }
> }
> say for reverse на r;
>
> На простых тестовых данных вроде работает, хотя я не уверен, что здесь
> все правильно и будет работать на других данных, например, если
> вставить большое число где-то на краю треугольника. Короче, на свалку.
Да, а из-за логики с отсечением по максимуму неправильно работает вариант
1
3 1
3 1 1
1 1 1 4
http://ideone.com/ECr6KQTn
>
> Третий подход через рекурсию. Даже получается уложиться в 256 байт,
> причем не убирая "my". Не очень понятно, правда, как отсеиваются
> неверные пути, но работает :-)
>
> for(1..<>){
> @v=();$h=<>;for(1..$h){push на v,[split/\s+/,<>]}
> print path(0,0),"\n";
> }
> sub path{
> my($x,$y)=@_;
> return 0 if $y==$h;
> my$l=path($x,$y+1);
> my$r=path($x+1,$y+1);
> $v[$y][$x]+($l>$r?$l:$r);
> }
Ну тут в принципе O(n^4) получается :) Даже 20 строк считаются 2 секунды.
> Но spoj.pl все равно говорит: "time limit exceeded" :-( Пробовал
> избавиться от повторных вычислений:
>
> for(1..<>){
> @p=();@v=();$h=<>;for(1..$h){push на v,[split/\s+/,<>]}
> print p(0,0),"\n";
> }
> sub p{
> my($x,$y)=@_;
> return $p[$y][$x]if defined $p[$y][$x];
> return 0 if $y==$h;
> my$l=p($x,$y+1);
> my$r=p($x+1,$y+1);
> return $p[$y][$x]=$v[$y][$x]+($l>$r?$l:$r);
> }
>
> И здесь "time limit exceeded". Если я правильно понимаю, все равно
> приходится пройтись по всем путям? Нет?
Да, по всем. Но с кэшированием уже вычисленных под-треугольников :)
Вернулись к моему алгоритму (только он считает рядами, поэтому и
кэширует один предыдущий ряд, больше не надо).
А другого способа и нет. Задача в том, чтобы быстро сложить 5000000
маленьких целых чисел. Непонятно, почему Питон успевает, а Перл — нет.
Скаляры-то одинаковые.
Подробная информация о списке рассылки Moscow-pm