Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Forum de l’article

Python, Scheme, C

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par les responsables.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.
Attention ! Si votre message contient un lien, il devra être validé par le webmestre. Inutile de le poster à nouveau ;-)

Lien hypertexte

(Si votre message se réfère à un article publié sur le Web, ou à une page fournissant plus d’informations, vous pouvez indiquer ci-après le titre de la page et son adresse.)

Rappel de la discussion
Python, Scheme, C
Jean-Baptiste Bianquis - le 26 juin 2020

En fait je n’avais pas bien réfléchi. La hauteur moyenne de l’arbre d’appels (c’est-à-dire l’espérance de l’espace nécessaire sur la pile) est exactement la hauteur moyenne d’un ABR aléatoire. Cette quantité a bien sûr été étudiée, et on montre assez facilement qu’elle est logarithmique en $n$ (et même inférieure à $3\log_2(n)$). Je ne connais pas la variance, mais elle est petite.

Conclusion : la limite de 1000 stack frames en Python (qu’on peut modifier dynamiquement, d’ailleurs) n’est pour rien dans l’histoire ! Évidemment, essayer de manipuler de tels tableaux en Python « pur » (sans Numpy ou autre) reste une mauvaise idée, j’en conviens.

Python, Scheme, C
Laurent Bloch - le 26 juin 2020

Bonjour, merci de vos contributions, elles sont en ligne. bc me dit :

$ bc -l
bc 1.07.1
l(200000000)
19.11382792451231078156

Donc ce n’est pas la profondeur de l’arbre de récursion, mais bien
probablement, comme vous le dites, l’encombrement de la mémoire,
et à force de page faults...

Bien à vous !

Derniers commentaires

Grands corps, grandes écoles, le conservatisme français
Bonjour Laurent, J’avais lu une partie du texte sur ton site... "ce qui expliquait le succès (…)

Une sacrée envie de foutre le bordel
Bonsoir Laurent Tu liras certainement avec beaucoup d’intérêt le chapitre "La seconde mort de (…)

Une sacrée envie de foutre le bordel
Demain je vais acheter le livre de Xavier Niel. Pourtant je connais son magnifique succès, (…)

Why Nations Fail : The Origins of Power, Prosperity, and Poverty
En lisant ces critiques je comprends que mon compte-rendu est trop incomplet : l’intérêt (…)

Intel, le déclin ?
Merci de tes explications, Vincent, je m’y range bien volontiers. Je me fie néanmoins à une (…)