sbcl fonctionne toujours sur le deuxième appel de la fonction

Question

La fonction:

Étant donné une liste LST retourner toutes les permutations de contenu de longueur k exactement, qui est par défaut de la liste à la longueur de la liste si non fourni.

(defun permute (lst &optional (k (length lst)))
  (if (= k 1)
   (mapcar #'list lst)
   (loop for item in lst nconcing
     (mapcar (lambda (x) (cons item x)) 
             (permute (remove-if (lambda (x) (eq x item)) lst) 
                      (1- k))))))

Le problème: J'utilise un biofilm dans emacs connectés à sbcl, je ne l'ai pas encore fait trop de personnalisation. La fonction fonctionne très bien sur les entrées plus petites comme lst = « (1 2 3 4 5 6 7 8) k = 3, qui est ce que ce sera surtout utilisé dans la pratique. Cependant, quand je l'appelle avec une grande entrée deux fois de suite le deuxième appel ne retourne jamais et sbcl ne montre même pas sur le dessus. Ce sont les résultats au REPL:

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))
Evaluation took:
12.263 seconds of real time
12.166150 seconds of total run time (10.705372 user, 1.460778 system)
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ]
99.21% CPU
27,105,349,193 processor cycles
930,080,016 bytes consed

(2 7 8 3 9 1 5 4 6 0)
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))

Et il ne revient jamais du deuxième appel. Je ne peux que deviner que, pour une raison que je fais quelque chose d'horrible au collecteur d'ordures, mais je ne vois pas quoi. Est-ce que quelqu'un a des idées?

Answer 1

Une chose qui ne va pas dans votre code est votre utilisation de EQ. EQ compare l'identité.

EQ n'est pas pour comparer les chiffres. EQ de deux nombres peut être vrai ou faux.

Utilisez EQL si vous voulez comparer par l'identité, des chiffres en valeur ou caractères. Non EQ.

En fait

(remove-if (lambda (x) (eql x item)) list)

est juste

(remove item list)

Pour votre code le bug EQ POURRAIENT signifie que permute est appelée dans l'appel récursif sans réellement un numéro retiré de la liste.

En dehors de cela, je pense que SBCL est juste occupé avec la gestion de la mémoire. SBCL sur mon Mac a acquis beaucoup de mémoire (plus d'un Go) et était occupé à faire quelque chose. Après un certain temps le résultat a été calculé.

Votre fonction récursive génère énorme quantité de « déchets ». LispWorks dit: 1360950192 octets

Peut-être que vous pouvez trouver une mise en œuvre plus efficace?

Mise à jour: déchets

Lisp fournit une gestion automatique de la mémoire, mais cela ne libère pas le programmeur de penser au sujet des effets de l'espace.

Lisp utilise à la fois une pile et le tas à allouer de la mémoire. Le tas peut-être structuré d'une certaine façon pour le GC - par exemple dans les générations, demi-espaces et / ou des zones. Il y a des éboueurs précis et éboueurs « conservateurs » (utilisés par SBCL sur les machines Intel).

Quand un programme fonctionne, nous pouvons voir les différents effets:

1. procédures récursives normales allouer de l'espace sur la pile. Problème:. La taille de la pile est généralement fixe (même si certains Lisps peuvent augmenter dans un gestionnaire d'erreur)

2. un programme peut allouer énorme quantité de mémoire et le retour d'un grand résultat. PERMUTE est une telle fonction. Il peut retourner des listes très grandes.

3. un programme peut allouer de la mémoire et de l'utiliser temporairement et le collecteur d'ordures peut le recycler. Le taux de création et de destruction peut être très élevé, même si le programme n'utilise une grande quantité de mémoire fixe.

Il y a plus de problèmes, cependant. Mais pour chacun des au-dessus du programmeur Lisp (et tous les autres programmeur utilisant une implémentation du langage avec la collecte des ordures) doit apprendre comment gérer cela.

1. Remplacer la récursivité par itération. Remplacer récursion avec récursion queue.

2. Afficher uniquement la partie du résultat qui est nécessaire et ne génère pas la solution complète. Si vous avez besoin de la permutation n-ième, puis calculer que toutes les permutations et non. Utilisez datastructures paresseux qui sont calculés sur la demande. Utilisez quelque chose comme série, qui permet d'utiliser un jet semblable, mais efficace, calcul. Voir SICP, PAIP, et d'autres livres Lisp avancés.

3. mémoire réutilisation avec un gestionnaire de ressources. tampons de réutilisation au lieu d'allouer tout le temps des objets. Utilisez un éboueur efficace avec un soutien particulier pour la collecte des objets éphémères (de courte durée). Parfois, il peut aussi aider à modifier les objets de façon destructive, au lieu d'attribuer de nouveaux objets.

Au-dessus de traite des problèmes d'espace des programmes réels. Idéalement nos compilateurs ou l'infrastructure d'exécution peuvent fournir un soutien automatique pour faire face à ces problèmes. Mais cela ne fonctionne pas vraiment en réalité. La plupart des systèmes Lisp offrent des fonctionnalités de bas niveau pour faire face à cela et Lisp fournit des objets mutables - parce que l'expérience des programmes de Lisp monde réel a montré que les programmeurs ne veulent les utiliser pour optimiser leurs programmes. Si vous avez une grande application de CAO qui calcule la forme d'aubes de turbine, puis des vues théoriques / puriste sur la mémoire non-mutables simplement ne pas appliquer -. Le développeur veut le code plus rapide / plus petit et l'empreinte d'exécution plus petit

Answer 2

SBCL sur la plupart des plates-formes utilise éboueur génération, ce qui signifie que la mémoire allouée qui survit plus un certain nombre de collections sera plus rarement considérée pour la collecte. Votre algorithme pour le cas de test donné génère autant de déchets qu'il déclenche GC tant de fois que les résultats réels, qui ont de toute évidence pour survivre à l'exécution entière de fonction, sont titulaires, qui est déplacé à une génération finale qui est recueillie soit très rarement ou pas du tout. Par conséquent, la deuxième exécution de la fonction, les paramètres standard pour les systèmes 32 bits, à court de tas (512 Mo, peut être augmentée avec des options d'exécution).

données permanent peuvent être déchets collectés en déclenchant manuellement le collecteur avec (sb-ext:gc :full t). Ceci est évidemment dépendant de l'implémentation.

Answer 3

De l'apparence de la sortie, vous êtes à la recherche à la boue-rempl, droit?

Essayez de changer le tampon « * * inférieur-lisp », vous verrez probablement que SBCL a chuté jusqu'à la LDB (débogueur intégré de bas niveau). Très probablement, vous avez réussi à faire sauter l'appel pile.