按值对哈希表进行排序的最佳方法是什么？

发布于 2024-12-06 01:02:30 字数 661 浏览 0 评论 0原文

现在我必须在排序之前将 hastable 复制到列表中：

(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))) ))

顺便说一句，获取列表的前 N 个元素的更好方法是什么？

原文

Now i have to copy the hastable to a list before sorting it:

(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, what's the better way to fetch the first N elements of a list ?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不打扰别人 2024-12-13 01:02:30

瓦廷的答案在技术上是正确的，但对于提出这个问题的人的直接问题可能不是很有帮助。使用哈希表来保存计数器集合，然后按分数选择前 N 个项目的常见情况可以如下完成：

;; 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))

第一个函数将哈希表的内容作为一系列 cons 列表中的对，称为关联列表（键/值对的典型列表表示）。大多数 Lisp 爱好者手头上已经有了这个函数的变体，因为它是一个非常常见的操作。该版本来自 Alexandria 库，该库在 CL 社区中使用非常广泛。

第二个函数使用 SUBSEQ 从通过使用每对 CDR 作为键对第一个函数返回的列表进行排序而返回的列表中获取前 N 个项目。将 :key 更改为 #'car 将按哈希键排序，将 #'> 更改为到 #'<会颠倒排序顺序。

Vatine's answer is technically correct, but probably not super helpful for the immediate problem of someone asking this question. The common case of using a hash table to hold a collection of counters, then selecting the top N items by score can be done like this:

;; 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))

The first function returns the contents of a hash table as a series of cons'd pairs in a list, which is called an association list (the typical list representation for key/value pairs). Most Lisp enthusiasts already have a variation of this function on hand because it's such a common operation. This version is from the Alexandria library, which is very widely used in the CL community.

The second function uses SUBSEQ to grab the first N items from the list returned by sorting the alist returned by the first function using the CDR of each pair as the key. Changing :key to #'car would sort by hash keys, changing #'> to #'< would invert the sort order.

回复收藏 0 原文