Quelle est la meilleure façon de trier une table de hachage par valeur ?

Question

Maintenant, je dois copier la table de hachage dans une liste avant de la trier :

(defun good-red ()
  (let ((tab (make-hash-table)) (res '()))
    (dotimes (i 33) (setf (gethash (+ i 1) tab) 0))
    (with-open-file (stream "test.txt")
        (loop for line = (read-line stream nil)
             until (null line)
             do
                (setq nums (butlast (str2lst (substring line 6))))
                (dolist (n nums) (incf (gethash n tab)))
                ))
    **(maphash #'(lambda (k v) (push (cons k v) res)) tab)**
    (setq sort-res (sort res #'< :key #'cdr))
    (reverse (nthcdr (- 33 18) (mapcar #'car sort-res))) ))

BTW, quelle est la meilleure façon de récupérer les N premiers éléments d'une liste ?

Answer 1

La réponse de Vatine est techniquement correcte, mais probablement pas super utile pour le problème immédiat de quelqu'un qui pose cette question. Le cas commun d'utilisation d'une table de hachage pour contenir une collection de compteurs, puis de sélection des N premiers éléments par score peut être fait comme ceci :

;; convert the hash table into an association list
(defun hash-table-alist (table)
  "Returns an association list containing the keys and values of hash table TABLE."
  (let ((alist nil))
    (maphash (lambda (k v)
               (push (cons k v) alist))
             table)
    alist))

(defun hash-table-top-n-values (table n)
  "Returns the top N entries from hash table TABLE. Values are expected to be numeric."
  (subseq (sort (hash-table-alist table) #'> :key #'cdr) 0 n))

La première fonction renvoie le contenu d'une table de hachage comme une série de contre dans une liste, qui est appelée liste d'association (la représentation typique de liste pour les paires clé/valeur). La plupart des amateurs de Lisp ont déjà une variante de cette fonction à portée de main, car c'est une opération très courante. Cette version est tirée du Alexandria qui est très largement utilisée dans la communauté CL.

La seconde fonction utilise SUBSEQ pour récupérer les N premiers éléments de la liste renvoyée par le tri de la liste renvoyée par la première fonction en utilisant le CDR de chaque paire comme clé. En remplaçant :key par #'car, on trie par les clés de hachage, et en remplaçant #'> par #'<, on inverse l'ordre de tri.

Answer 2

Une table de hachage est par nature non ordonnée. Si vous voulez qu'elle soit triée, vous devez initialiser une sorte de structure de données ordonnée avec son contenu.

Si vous voulez récupérer les N premiers éléments d'une séquence, il y a toujours SUBSEQ.