Bizzareries d'Ackermann

Bonjour,

La subtilité est dans le $Ack[$_[0]][$_[1]]. Le résultat de l'appel à
la fonction est stocké en mémoire, ce qui fait qu'un nombre minimal
d'appels à la fonction est nécessaire (si ack(32,12) a été appelé une
fois, $Ack[32][12] contient le résultat, donc si on a besoin de
ack(32,12) à un autre moment dans le code il ne sera pas nécessaire de
refaire un appel à la fonction.

Espérant être clair (j'en doute un peu),

--
Denis

Le 20 mai 2005, Denis -esp2008- a écrit dans fr.comp.lang.perl :

La subtilité est dans le $Ack[$_[0]][$_[1]]. Le résultat de l'appel à
la fonction est stocké en mémoire,

Où ça ? Automatiquement ?

ce qui fait qu'un nombre minimal
d'appels à la fonction est nécessaire (si ack(32,12) a été appelé une
fois, $Ack[32][12] contient le résultat, donc si on a besoin de
ack(32,12) à un autre moment dans le code il ne sera pas nécessaire de
refaire un appel à la fonction.

Tu veux dire que si $Ack[32][12] existe, Perl (l'interpréteur) renverra la
valeur de $Ack[32][12] sans interpréter la fonction Ack ? Ca me parrait
bien étrange, car $Ack[32][12] est initialisé à 12 lors du premier appel à
Ack(32,12), et il n'y a pas d'autre affectation. J'ai plutôt l'impression
que c'est la valeur du second argument qui est mise en cache. Mais je ne
comprend pas comment cela accélère l'éxécution.

On Fri May 20 2005 at 13:51, Jogo wrote:

Cette version va presque 500 fois plus vite que son équivalent sans
optimisation :

Pour le 500 fois, je suppose que ça dépend des paramètres. Et comme la
fonction d'Ackermann explose et que les calculs ne sont pas faits avec
entiers "long", ça ne doit pas changer grand chose, on doit vite
rencontrer la limite.

Mais je ne comprend pas du tout pourquoi... Qu'est-ce que cette variable
homonyme à la fonction ? Un cache ?

Oui. C'est le fait qu'elle porte le même nom qui vous gène ? (moi,
c'est plutôt la syntaxe ultra-compacte et difficilement lisible)

Les espaces de nommages des différents bestiaux Perl sont séparés.
@x $x et &x sont trois symboles différents.

--
arboi@alussinan.org http://arboi.da.ru
NASL2 reference manual http://michel.arboi.free.fr/nasl2ref/

"Jogo" <jogo@alussinan.org> a écrit dans le message de news:
Xns965C8CEBF5EBCjogoecolemontechlarr@192.168.10.8...

Salut,

En trainant sur http://shootout.alioth.debian.org/benchmark.php, je suis
tombé sur cette version optimisée de la fonction d'Ackermann :

sub Ack {
$_[0] ? ($Ack[$_[0]][$_[1]] ||= $_[1] ? Ack($_[0]-1, Ack($_[0], $_[1]-1))
: Ack($_[0]-1, 1))
: $_[1]+1;
}

Cette version va presque 500 fois plus vite que son équivalent sans
optimisation :

sub Ack {
$_[0] ? ($_[1] ? Ack($_[0]-1, Ack($_[0], $_[1]-1))
: Ack($_[0]-1, 1))
: $_[1]+1;
}

Mais je ne comprend pas du tout pourquoi... Qu'est-ce que cette variable
homonyme à la fonction ? Un cache ?

la réponse est certainement la:
http://perl.plover.com/MiniMemoize/memoize.html

--
dominix

À (at) Fri, 20 May 2005 13:51:11 +0200,
Jogo <jogo@alussinan.org> écrivait (wrote):

Salut,

En trainant sur http://shootout.alioth.debian.org/benchmark.php, je suis
tombé sur cette version optimisée de la fonction d'Ackermann :

sub Ack {
$_[0] ? ($Ack[$_[0]][$_[1]] ||= $_[1] ? Ack($_[0]-1, Ack($_[0], $_[1]-1))
: Ack($_[0]-1, 1))
: $_[1]+1;
}

Qu'on peut réécrire en :

{ # pour cacher le cache ;-)
my @ack_cache;
sub Ack {
if ($_[0]) {
if (not $ack_cache[$_[0]][$_[1]]) {
if ($_[1]) {
$ack_cache[$_[0]][$_[1]] = Ack($_[0]-1, Ack($_[0], $_[1]-1));
} else {
$ack_cache[$_[0]][$_[1]] = Ack($_[0]-1, 1);
}
}
return $ack_cache[$_[0]][$_[1]];
} else {
return $_[1]+1;
}
}
}

qui est (peut-être) plus clair mais qui a surtout l'avantage de ne pas polluer
l'espace de nommage avec un tableau (@Ack ou @ack_cache).

Mais je ne comprend pas du tout pourquoi... Qu'est-ce que cette variable
homonyme à la fonction ? Un cache ?

C'est bien un cache... Perl distingue les objets de types différents ($, @, %,
&, etc) et de même nom. Pour en savoir plus, lire perldata et perlmod...

--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
Perl en français - <http://perl.enstimac.fr/>

On Fri May 20 2005 at 15:45, Jogo wrote:

Où ça ? Automatiquement ?

C'est plus clair comme ça ? C'est rigoureusement équivalent.

sub Ack {
my ($a, $b) = @_;
if ($a != 0) {
if ($Cache[$a][$b]) {
return $Cache[$a][$b];
} else {
if ($b != 0) {
$Cache[$a][$b] = Ack($a - 1, (Ack($a, $b - 1)));
} else {
$Cache[$a][$b] = Ack($a - 1, 1);
}
return $Cache[$a][$b];
}
} else {
return $b + 1;
}
}

J'ai plutôt l'impression que c'est la valeur du second argument qui
est mise en cache.

C'est le résultat qui est caché.

Mais je ne comprend pas comment cela accélère l'éxécution.

Avec cache :
Ack[0][1]=2
Ack[1][0]=2
Ack[0][2]=3
Ack[1][1]=3
Ack[2][0]=3
Cache[1][1]=3
Ack[0][3]=4
Ack[1][2]=4
Ack[0][4]=5
Ack[1][3]=5
Ack[2][1]=5
Cache[1][3]=5
Ack[0][5]=6
Ack[1][4]=6
Ack[0][6]=7
Ack[1][5]=7
Ack[2][2]=7

Sans cache :
Ack[0][1]=2
Ack[1][0]=2
Ack[0][2]=3
Ack[1][1]=3
Ack[2][0]=3
Ack[0][1]=2
Ack[1][0]=2
Ack[0][2]=3
Ack[1][1]=3
Ack[0][3]=4
Ack[1][2]=4
Ack[0][4]=5
Ack[1][3]=5
Ack[2][1]=5
Ack[0][1]=2
Ack[1][0]=2
Ack[0][2]=3
Ack[1][1]=3
Ack[0][3]=4
Ack[1][2]=4
Ack[0][4]=5
Ack[1][3]=5
Ack[0][5]=6
Ack[1][4]=6
Ack[0][6]=7
Ack[1][5]=7
Ack[2][2]=7

Le 23 mai 2005, Michel Arboi a écrit dans fr.comp.lang.perl :

Où ça ? Automatiquement ?

C'est plus clair comme ça ? C'est rigoureusement équivalent.

sub Ack {
my ($a, $b) = @_;
if ($a != 0) {
if ($Cache[$a][$b]) {
return $Cache[$a][$b];
} else {
if ($b != 0) {
$Cache[$a][$b] = Ack($a - 1, (Ack($a, $b - 1)));
} else {
$Cache[$a][$b] = Ack($a - 1, 1);
}
return $Cache[$a][$b];
}
} else {
return $b + 1;
}
}

Vous êtes vraiment sûr que c'est équivalent à :
sub Ack {
$_[0] ? ($Ack[$_[0]][$_[1]] ||= $_[1] ? Ack($_[0]-1, Ack($_[0], $_[1]-1))
: Ack($_[0]-1, 1))
: $_[1]+1;
}


Parce qu'avec votre 'traduction' (ou celle de Paul Gabori), je comprend
très bien. C'est cette 'traduction' qui m'intrigue. Moi, j'aurais plustôt
traduit ça par :

sub Ack {
my ($a,$b) = @_ ;
if ($a) {
if ($Cache[$a][$b] || $b) {
$Cache[$a][$b] = 1 ;
return Ack($a-1, Ack($a,$b-1)) ;
} else {
return Ack($a-1,1) ;
}
} else {
return $b+1 ;
} ;
} ;

Où est mon erreur, bon sang ?

Où est mon erreur, bon sang ?

Ca y est j'ai trouvé. En fait c'est que la précédence de ||= est inférieure
à celle de ?:. Je croyais que ||= avait la même précédence que ||.
Je suis vraiment désolé du dérangement.

À (at) Tue, 24 May 2005 11:03:57 +0200,
Jogo <jogo@alussinan.org> écrivait (wrote):

Où est mon erreur, bon sang ?

Peut-être dans l'interprétation du "||=". Le || est paresseux !

Lorsque j'écris :

$a ||= ...; # où "..." est une expression Perl quelconque.

Si $a contient déjà une valeur vrai, l'expression ... n'est même pas évaluée.

--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
Perl en français - <http://perl.enstimac.fr/>

À (at) Tue, 24 May 2005 12:41:14 +0200,
Jogo <jogo@alussinan.org> écrivait (wrote):

Ca y est j'ai trouvé. En fait c'est que la précédence de ||= est inférieure
à celle de ?:. Je croyais que ||= avait la même précédence que ||.

En fait tous les opérateurs composés (+=, -=, ||=, etc.) sont exactement au
même niveau de priorité que l'opérateur =.


--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
Perl en français - <http://perl.enstimac.fr/>