Dans Emacs Lisp, comment obtenez-vous une seule clé de hachage?

Question

Le problème que j'essaie de résoudre est de trouver le plus petit nombre de sous-arbres dans un graphe non orienté où chaque noeud est dans un sous-arbre.

Mon algorithme est le suivant:

make a hash as follows 
    key= each node, 
    value= all nodes directly accessible from the key node 
    if a node has no edges it still has a key/value pair in the hash 
    each edge will be represented twice, once each direction 
loop until hash is empty 
    get any hash key/value pair 
    save the value to the working-list 
    remove the key/value from the hash 
    in a loop until the working-list is empty 
    (when (gethash (car working-list) hash) 
     concatenate value to the end of the working-list 
     (remhash (car working-list) hash)) 
    (pop working-list) 
    When the loop is finished you have removed all nodes and edges in a single subtree from the hash. 
    Increment number of subtrees. 
end loop until the hash is empty. 
report number of subtrees 

Voici le code:

(defun count-subtrees (hash) 
; hash 
;  key= each node, 
;  value= all nodes directly accessible from the key node 
; if a node has no edges it still has a key/value pair in the hash 
; each edge will be represented twice, once each direction 

(let ((number-of-trees 0)) 
    (while (setf key (anykey-in-hash hash))  ; this is where I need any key in the hash 
    (setf working-list (gethash key hash)) 
    (remhash key hash) 
    (while (gethash (car working-list) hash) 
     (setf working-list (append working-list 
           (gethash (car working-list hash)))) 
     (remhash (car working-list) hash) 
     (pop working-list)) 
    (incf number-of-trees)) 
    number-of-trees)) 

Je ne veux pas itérer sur les clés, je veux obtenir un seul.

REMARQUES:

Merci à tous d'avoir répondu. Je vous adresse ces commentaires.

Un éditeur a modifié ma question en ajoutant le mot "aléatoirement". Je m'en fous si c'est aléatoire ou pas. La réponse:

(defun anykey-in-hash (hash-table) 
    (block nil 
     (maphash (lambda (k v) (return (values k v))) 

est une solution parfaite.

J'ai utilisé par inadvertance 'while' (que j'ai trouvé dans le livre de Paul Graham) sans le définir. J'espère que cela n'a pas dérouté personne.

J'ai également utilisé setf au lieu de laisser définir des variables. Erreur stupide, je ne ferais jamais vraiment ça. Au début, j'ai une liste de toutes les clés. Mais pendant l'algorithme, les paires clé/valeur sont supprimées. C'est pourquoi j'ai besoin de laisser quelqu'un. J'utilise également la liste de travail sous forme de liste. La liste de travail contient certains des noeuds d'un sous-arbre. Tous ces nœuds (et leurs enfants * et les enfants de leurs enfants ...) doivent être retirés du hachage. L'ajout à cette liste consistait à simplifier le code. Dans une application réelle, j'utiliserais une autre structure de données, probablement une liste de listes. Mais je sentais que le faire ici ajouterait de la complexité sans rien ajouter au sens de la question.

* Lorsque je dis enfants, je veux dire utiliser le nœud comme une clé pour le hachage, la valeur est une liste des enfants.

Answer 1

Vous définissez des variables globales sans les déclarer au préalable, ce qui n'est pas portable et généralement dangereux en raison d'effets de bord; préfère laisser les fixations.

En ce qui concerne l'obtention des clés « aléatoires », vous pouvez simplement mettre en œuvre anykey-in-hash comme ceci:

(defun anykey-in-hash (hash-table) 
    (block nil 
    (maphash (lambda (k v) (return (values k v))) 
      hash-table))) 

L'ordre des éléments stockés dans une table de hachage dépend de la mise en œuvre, de sorte que maphash itérera sur les entrées dans un arbitraire (mais probablement déterministe) ordre. Si vous avez vraiment besoin d'un ordre aléatoire, c'est-à-dire un ordre qui peut changer avec différentes invocations de la fonction avec les mêmes arguments, vous devez collecter les clés et en choisir une aléatoirement.

Dans votre exemple, il semble que vous ayez seulement besoin de calculer la liste des clés une fois, pas à chaque itération de la boucle while. Je voudrais personnellement obtenir toutes les clés dans une liste, shuffle une fois, puis pop éléments de celui-ci au besoin. J'ai d'abord pensé que le code était en Common Lisp.En CL, Alexandria library définit shuffle (et random-elt), ainsi que hash-table-keys (ou hash-table-alist si vous avez besoin de la clé et de la valeur). En Emacs Lisp, vous pouvez facilement implémenter hash-table-keys avec maphash aussi (vous appuyez sur la touche devant une liste depuis l'intérieur de la fonction appelée par maphash). Si vous avez Emacs 24.4, vous pouvez (require 'subr-x) et appelez get-hash-keys. Mélanger peut être fait comme dans CL, vous pouvez adapter l'algorithme d'Alexandrie (https://gitlab.common-lisp.net/alexandria/alexandria/blob/master/sequences.lisp#L90), sachant que vous vous souciez seulement du cas où l'argument est une liste.