emacs - 从哈希表中检索键，按值排序，高效

Question

我正在使用 Emacs Lisp，但加载了 cl 包，用于 一些 常见的 lisp 功能。

我有一个包含多达 50K 个条目的哈希表，整数键映射到三元组，就像这样(但在实际的 lisp 中):

{
  8   => '(9  300 12)
  27  => '(5  125 9)
  100 => '(10 242 14)
}

三元组中的第二个值是在构建哈希表的复杂算法中计算得出的分数。我需要收集一个常规的 lisp 列表，其中包含哈希中的所有键，按分数排序(即所有键按值的 cadr 排序)。

所以对于上面的内容，我需要这个列表:

'(27 100 8)

我目前分两个阶段进行此操作，感觉效率低于需要的水平。

有什么好的方法吗？

我当前的解决方案使用 maphash 将键和值收集到两个新列表中，然后以正常方式进行 sort，引用中的分数列表谓词。不过，感觉我可以将收集和排序结合在一起。

编辑 |我也不喜欢使用哈希表，尽管我确实需要对整数键进行恒定的访问时间，这些键不是线性间隔的。

编辑 2|看起来实现二叉树排序是可行的，其中树中的标签是分数，值是键...这样我在映射哈希时进行排序。

...继续阅读有关排序算法的维基百科页面

Answer 1

基本上，您的解决方案是正确的:您需要将 key 收集到一个列表中:

(defun hash-table-keys (hash-table)
  (let ((keys ()))
    (maphash (lambda (k v) (push k keys)) hash-table)
    keys))

然后对列表进行排序:

(sort (hash-table-keys hash-table)
      (lambda (k1 k2)
        (< (second (gethash k1 hash-table))
           (second (gethash k2 hash-table)))))

可以将键收集与排序相结合:您需要将键收集到树中，然后“展平”树。但是，这仅在您处理非常大的表时才重要。此外，由于 Emacs Lisp 编译为字节码，您可能会发现使用内置的 sort 仍然比使用树更快。还要考虑开发成本 - 您将需要编写主要具有教育值(value)的代码。

深入研究，收集键分配键列表(无论如何你肯定需要它来获得结果)并且 sort 操作“就地”，所以“简单方法”大约是尽善尽美。

“树”方式将分配树(与所需的键列表相同的内存占用)并填充和展平它将是相同的 O(n*log(n)) 过程作为“收集+排序”的方式。然而，保持树平衡，然后“就地”展平它(即，不分配新列表)并不是一个简单的练习。

底线是:KISS .