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

[Alex Kapranoff]

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
маленьких целых чисел. Непонятно, почему Питон успевает, а Перл — нет.
Скаляры-то одинаковые.