Comment votre langage préféré gère-t-il la récursion profonde ?[fermé]
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai récemment commencé à apprendre Python et j'ai été plutôt surpris de trouver une limite de récursion profonde de 1000 (par défaut).Si vous le définissez suffisamment haut, environ 30 000, il plante avec une erreur de segmentation, tout comme C.Cependant, C semble aller beaucoup plus haut.
(Les gens de Python n'hésitent pas à souligner que vous pouvez toujours convertir des fonctions récursives en fonctions itératives et qu'elles sont toujours plus rapides.C'est vrai à 100%.Mais ce n'est pas vraiment le sujet de ma question.)
J'ai essayé la même expérience en Perl et environ 10 millions de récursions ont consommé la totalité de mes 4 Go de RAM et j'ai utilisé ^C pour arrêter d'essayer.De toute évidence, Perl n'utilise pas la pile C, mais il utilise une quantité ridicule de mémoire lors de ses récurrences - ce qui n'est pas très choquant compte tenu de la quantité de travail qu'il doit effectuer pour appeler des fonctions.
J'ai essayé dans Pike et j'ai été complètement surpris d'obtenir 100 000 000 de récursions en 2 secondes environ.Je n'ai aucune idée de comment il a fait cela, mais je soupçonne que cela a aplati la récursion en un processus itératif - il ne semble pas consommer de mémoire supplémentaire pendant qu'il le fait.[Note:Pike aplatit les cas triviaux, mais fait des erreurs de segmentation sur les plus compliqués, du moins c'est ce qu'on me dit.]
J'ai utilisé ces fonctions autrement inutiles :
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
Je suis très curieux de savoir comment d'autres langages (par exemple PHP, Ruby, Java, Lua, Ocaml, Haskell) gèrent la récursivité et pourquoi ils la gèrent de cette façon.De plus, veuillez noter si cela fait une différence si la fonction est "queue-récursive" (voir commentaire).
La solution
& "Les gens de Python savent rapidement que vous pouvez toujours convertir les fonctions récursives en fonctions itératives et qu'elles sont toujours plus rapides &";
C'est vrai, mais si c'est vraiment aussi simple que cela, pourquoi Python ne le fait-il pas pour moi, afin que mon code puisse paraître aussi simple que possible? (Je dis cela non pas pour claquer les développeurs Python, mais parce que la réponse explique le problème).
Les optimisations de récursivité sont présentes dans les langages fonctionnels depuis le 14e siècle ou quelque chose comme ça. Les implémentations Haskell, CAML, Lisp convertissent généralement au moins les fonctions récursives en itérations: vous le faites en notant qu'il est possible, c'est-à-dire que la fonction peut être réorganisée de sorte qu'aucune variable locale autre que la valeur de retour ne soit utilisée après l'appel récursif. . Une astuce pour rendre cela possible si certains travaux sont effectués sur la valeur de retour récursive avant retour, consiste à introduire un & "Accumulateur &" Supplémentaire; paramètre. En termes simples, cela signifie que le travail peut être effectué de la manière & Quot; down & Quot; au lieu de sur le chemin & "up &"; recherchez "comment créer une fonction récursive" pour plus de détails.
Les détails concrets de la conversion d'une fonction récursive en boucle dans une boucle servent essentiellement à bouger avec votre convention d'appel de telle sorte que vous pouvez & "exécuter l'appel &"; simplement en configurant les paramètres et en revenant au début de la fonction, sans se soucier de sauvegarder tout ce que vous ne voudriez jamais utiliser. En termes d'assembleur, il n'est pas nécessaire de conserver les registres de sauvegarde des appels si l'analyse du flux de données vous indique qu'ils sont inutilisés au-delà de l'appel. Il en va de même pour tout ce qui est sur la pile: vous n'avez pas à déplacer le pointeur de la pile. sur un appel si cela ne vous dérange pas & "; votre &"; peu de pile en cours de gribouillage par la prochaine récursivité / itération.
Contrairement à la façon dont vous avez paraphrasé les gens de Python, la conversion d'une fonction récursive générale en une itération n'est pas anodine: par exemple, si elle est multi-récursive, vous aurez toujours besoin d'une pile.
La mémorisation est une technique utile, cependant, pour les fonctions arbitrairement récursives, que vous voudrez peut-être rechercher si les approches possibles vous intéressent. Cela signifie que chaque fois qu'une fonction est évaluée, vous collez le résultat dans un cache. Pour utiliser ceci afin d'optimiser la récursion, si votre fonction récursive compte & "Down &" Et si vous la mémorisez, vous pouvez l'évaluer de manière itérative en ajoutant une boucle qui compte & "Up < !> quot; calculer chaque valeur de la fonction à tour de rôle jusqu'à atteindre la cible. Cela utilise très peu d’espace de pile à condition que le cache du mémo soit suffisamment grand pour contenir toutes les valeurs nécessaires: par exemple, si f (n) dépend de f (n-1), f (n-2) et f (n -3) vous avez seulement besoin d’espace pour 3 valeurs dans le cache: en montant, vous pouvez lancer l’échelle. Si f (n) dépend de f (n-1) et de f (n / 2), vous avez besoin de beaucoup d’espace dans le cache, mais toujours inférieur à celui que vous utiliseriez pour la pile dans une récursivité non optimisée.
Autres conseils
Il s’agit plus d’une question de mise en œuvre que d’une question de langue. Rien n'empêche certains implémenteurs du compilateur C (stoopid) de limiter également leur pile d'appels à 1 000. Il existe de nombreux petits processeurs qui ne disposeraient même pas d'espace de pile.
(Les gens de Python soulignent rapidement que vous pouvez toujours convertir des fonctions récursives en fonctions itératives et qu'elles sont toujours plus rapides. C'est vrai à 100%. Ce n'est pas vraiment ce sur quoi ma question porte.)
Peut-être qu'ils disent cela, mais ce n'est pas tout à fait correct. La récursivité peut toujours être convertie en itération, mais elle nécessite parfois aussi l'utilisation manuelle d'une pile . Dans ces circonstances, la version récursive pourrait être plus rapide (en supposant que vous êtes suffisamment intelligent pour effectuer des optimisations simples, comme extraire des déclarations inutiles en dehors de la routine récursive). Après tout, les poussées de pile entourant les appels de procédure constituent un problème bien délimité que votre compilateur devrait savoir optimiser. Les opérations de pile manuelles, en revanche, ne comporteront pas de code d’optimisation spécialisé dans votre compilateur et sont susceptibles de comporter toutes sortes de contrôles de cohérence de l’interface utilisateur qui prendront des cycles supplémentaires.
Il se peut que la solution itérative / pile soit toujours plus rapide en Python . Si c'est le cas, c'est un échec de Python, pas de la récursivité.
PHP a une limite par défaut de 100 avant de mourir:
Fatal error: Maximum function nesting level of '100' reached, aborting!
Modifier: vous pouvez modifier la limite avec ini_set('xdebug.max_nesting_level', 100000);, mais si vous dépassez environ 1150 itérations, PHP plante:
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C # /. NET utilisera la récursion de la queue dans un ensemble particulier de circonstances. (Le compilateur C # n'émet pas d'opcode tailcall, mais le JIT implémentera dans certains cas la récursion de la queue .
Shri Borde publie également un post sur ce sujet . Bien sûr, le CLR change continuellement et, avec .NET 3.5 et 3.5SP1, il a peut-être changé à nouveau en ce qui concerne les appels en fin de ligne.
À l'aide de ce qui suit dans la console interactive F #, il s'est exécuté en moins d'une seconde:
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
J'ai ensuite essayé une traduction directe, c'est-à-dire.
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
Même résultat mais compilation différente.
Voici à quoi f se présente lorsqu'il est traduit en C #:
int f(int i, int l)
{
while(true)
{
int num = i;
if(num >= l)
return l;
int i = num;
l = l;
i = i + 1;
}
}
g , est toutefois traduit en ceci:
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
Il est intéressant de noter que deux fonctions fondamentalement identiques sont rendues différemment par le compilateur F #. Il montre également que le compilateur F # a une optimisation de la queue récursive. Ainsi, cela devrait boucler jusqu'à ce que i atteigne la limite pour les entiers 32 bits.
Selon ce fil, environ 5 000 000 avec java, 1 Go de RAM. (et cela, avec la version 'client' du hotspot)
C'était avec une pile (-Xss) de 300 Mo.
Avec une option de serveur , qui pourrait être augmenté.
On peut aussi essayer d’optimiser le compilateur ( avec JET , par exemple) pour réduire le superposer à chaque couche.
Dans certains cas non pathologiques (comme le vôtre), Lua utilisera récursion d'appels de queue , c'est-à-dire il va juste sauter sans mettre les données en pile. Le nombre de boucles de récursivité peut donc être presque illimité.
Testé avec:
function f(i, l)
if i < l then
return f(i+1, l)
end
return i
end
local val1 = arg[1] or 1
local val2 = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))
Aussi avec:
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
et même essayé la récursion croisée (f en appelant g et g en appelant f ...).
Sous Windows, Lua 5.1 utilise environ 1,1 Mo (constante) pour l’exécuter et s’achève en quelques secondes.
Exécution de Ruby 1.9.2dev (révision 28618 du 11/07/2010) [x86_64-darwin10.0.0] sur un ancien macbook blanc :
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
génère 9353 pour moi, ce qui signifie que Ruby se débrouille avec moins de 10 000 appels sur la pile.
Avec récursion croisée, comme :
def f
@i += 1
g
end
def g
f
end
il chie en deux fois moins de temps, à 4677 (~= 9353/2).
Je peux effectuer quelques itérations supplémentaires en encapsulant l'appel récursif dans un proc :
def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
qui atteint 4850 avant de se tromper.
Visual Dataflex créera un débordement de pile.
Je suis un fervent partisan de la programmation fonctionnelle et, comme la plupart de ces langages implémentent l'optimisation des appels en queue, vous pouvez récifuer autant que vous le souhaitez :-P
Cependant, pratiquement, je dois utiliser beaucoup de Java et utiliser beaucoup Python. Aucune idée de la limite de Java, mais pour Python, j'avais prévu (mais ne l'ai pas encore fait) d'implémenter un décorateur qui optimiserait la fonction décorée. J'avais prévu de ne pas optimiser la récursivité, mais plutôt d'exercer une correction dynamique du bytecode Python et d'en apprendre davantage sur les éléments internes de Pythons. Voici quelques liens intéressants: http://lambda-the-ultimate.org/node/1331 et http://www.rowehl.com/blog/?p=626
Il existe un moyen d'améliorer le code Perl, de lui faire utiliser une pile de taille constante. Vous faites cela en utilisant une forme spéciale de goto.
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
Lors de son premier appel, il allouera de l’espace sur la pile. Ensuite, il va changer ses arguments et redémarrer le sous-programme, sans rien ajouter de plus à la pile. Il va donc prétendre qu'il ne s'est jamais appelé lui-même, le transformant en un processus itératif.
Vous pouvez également utiliser le Sub :: Call :: Recur module. Ce qui rend le code plus facile à comprendre et plus court.
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
clojure fournit un formulaire spécial pour la récursion de la queue & "; se reproduire &"; cela ne peut être utilisé que dans les endroits de la queue de l'ast. Sinon, il se comporte comme java et lève probablement une exception StackverflowException.
