6

我正在使用 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| 看起来实现二叉树排序可以工作，其中树中的标签是分数，值是键......这样我在映射哈希时进行排序。

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

4

1 回答 1

9

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

(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内置的仍然比使用树更快。还要考虑开发成本 - 您将需要编写其价值主要用于教育的代码。

深入研究，收集密钥分配密钥列​​表（无论如何您肯定需要结果）并sort“就地”操作，因此“简单方法”几乎和它一样好。

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

底线是：亲吻。

于 2013-06-12T13:47:08.393 回答