emacs – 从哈希表中检索密钥,并按值有效排序

来源：互联网收集：自由互联发布时间：2021-06-16

我正在使用Emacs Lisp,但加载了cl包,用于一些常见的lisp功能. 我有一个包含多达50K条目的哈希表,整数键映射到三元组,类似这样(但在实际的lisp中)： { 8 = '(9 300 12) 27 = '(5 125 9) 100 = '(10 242

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

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

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

三元组中的第二个值是在构建散列表的复杂算法期间计算的分数.我需要收集一个常规的lisp列表,其中包含来自散列的所有密钥,按分数排序(即由值的cadr排序的所有密钥).

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

'(27 100 8)

我目前正在做两个阶段,感觉效率低于它需要的阶段.

有没有办法做到这一点？

我当前的解决方案使用maphash将键和值收集到两个新列表中,然后以正常方式进行排序,参考谓词中的分数列表.但是,我觉得我可以将收集和排序结合起来.

编辑|我也不依赖于使用哈希表,尽管我确实需要对整数键的持续访问时间,这些键不是线性间隔的.

编辑2 |看起来实现二叉树排序可能会起作用,树中的标签是分数,值是键……这样我就可以在哈希映射时进行排序.

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

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

(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编译为字节码,您可能会发现使用内置排序仍然比使用树更快.还要考虑开发成本 – 您需要编写其价值主要是教育性的代码.

深入研究,收集密钥会分配密钥列表(结果肯定需要这些密钥),并且排序操作“就地”,因此“简单方法”就像它获得的一样好.

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

底线是：KISS.

相关文章