Bizzareries d'Ackermann

Le
Jogo
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 ?
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Denis -esp2008-
Le #60644
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
Jogo
Le #60643
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.

Michel Arboi
Le #60642
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.

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

DoMinix
Le #60343
"Jogo"
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

Paul Gaborit
Le #60339
À (at) Fri, 20 May 2005 13:51:11 +0200,
Jogo
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 - Perl en français -
Michel Arboi
Le #60338
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

Jogo
Le #60335
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 ?


Jogo
Le #60019
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.

Paul Gaborit
Le #60017
À (at) Tue, 24 May 2005 11:03:57 +0200,
Jogo
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 - Perl en français -
Paul Gaborit
Le #60016
À (at) Tue, 24 May 2005 12:41:14 +0200,
Jogo
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 - Perl en français -
Publicité
Poster une réponse
Anonyme