перестановки

[ocehb]

sub shuffle (@) {
    return ( [ $_[0],$_[1] ],[ $_[1],$_[0] ] ) if (scalar @_ == 2);

    my $b = shift @_;
    my @ret;
    foreach my $r (shuffle (@_)) {
        foreach (0..scalar @$r) {
            my (@rr) = @$r;
            splice @rr,$_,0,$b;
            push @ret,\@rr;
        }
    }
    return @ret;
}

# time perl a.pl 1 2 3 4 5 6 | wc -l
     720
Real: 0.07s User: 0.05s System: 0.01s Percent: 90%% Cmd: perl a.pl 1 2 3 4 5 6
Real: 0.07s User: 0.00s System: 0.00s Percent: 5%% Cmd: wc -l
# time perl a.pl 1 2 3 4 5 6 7 8 9 | wc -l
  362880
Real: 7.43s User: 6.65s System: 0.63s Percent: 98%% Cmd: perl a.pl 1 2 3 4 5 6 7 8 9
Real: 7.42s User: 0.07s System: 0.01s Percent: 1%% Cmd: wc -l
# time perl a.pl 1 2 3 4 5 6 7 8 9 0 | wc -l
Out of memory during request for 1012 bytes, total sbrk() is 536786944 bytes!
       0
Real: 56.49s User: 16.54s System: 4.47s Percent: 37%% Cmd: perl a.pl 1 2 3 4 5 6 7 8 9 0
Real: 56.49s User: 0.00s System: 0.00s Percent: 0%% Cmd: wc -l
#

Comments

[rmrfchik.livejournal.com]

Потому что не умеют ею пользоваться. Или выбирают не те средства (без tail recursion).

Вариантов много

[alll]

Или, например, встречали некоторое количество народу, который не умеет ею пользовацо.

[alll]

А tail recursion к cpp ещё вроде не прикрутили. Хотя именно это не особая проблема - дело было при разработке прототипа, нужно было быстро выдать на-гора работоспособную версию с пофиг каким быстродействием.

[rmrfchik.livejournal.com]

До меня доходили слухи, что в каких-то простейших случаях gcc умеет tail recursion (сворачивать рекурсию в итерацию). Про другие компиляторы не в курсе. Но, в любом случае, сам язык не способствует остаточной рекурсии.

хех. умеет :)

[ocehb]

# gcc -xc =(cat)
#include <stdio.h>
#include <stdlib.h>

int ff (int i)
{
        if (i == 1) return 0;
        return i + ff (i-1);
}

int main (int argc,char** argv)
{
        int num = atoi (argv[1]);

        printf ("%d => %d\n",num,ff (num));
        exit (0);
}
^D
# time ./a.out 10240000
10240000 => 139337727
Real: 1.28s User: 0.26s System: 0.31s Percent: 44%% Cmd: ./a.out 10240000
# 

Re: хех. умеет :)

[rmrfchik.livejournal.com]

Так здесь нет остаточной рекурсии.

Re: хех. умеет :)

[ocehb]

может чего и не понимаю, но по http://en.wikipedia.org/wiki/Tail_recursion, это оно...

Re: хех. умеет :)

[rmrfchik.livejournal.com]

Не понимаешь.
Давай рассмотрим вот это:
return i + ff (i-1);
Домашнее задание, выдели тут последюю операцию. Даю маячок, эта конструкия семантически экваивалентна:
return ff (i-1) + i;
Дальше продолжать?

Re: хех. умеет :)

[ocehb]

ладно, нет времени спорить :)
дома разберемся.

Re: хех. умеет :)

[rmrfchik.livejournal.com]

А чего тут спорить-то?
Так и говори — "каюсь, слил".
Последняя операция в return i+ff(i-1) это +. Хорошо заметно, если переписать в лисповом стиле (не зря примеры в статье приведены на лиспе): (+ i (ff (- i 1)))
А вот как будет выглядет остаточная рекурсия:

int ff (int i, int acc)
{
if (i == 1) return acc;
return ff (i-1, acc + i);
}
int main (int argc,char** argv)
{
int num = atoi (argv[1]);
printf ("%d => %d\n",num,ff (num,0));
exit (0);
}

Re: хех. умеет :)

[ocehb]

да до этого я дошел уже, просто бегать сегодня надо.

Re: хех. умеет :)

[lispnik.livejournal.com]

Нет, не оно :)
А gcc действительно умеет превращать хвостовую рекурсию в цикл, но только если список аргументов достаточно простой...