在Emacs Lisp中,如何获得单个散列键?
我试图解决的问题是在非有向图中找到最少数量的子树,其中每个节点都在子树中。在Emacs Lisp中,如何获得单个散列键?
我的算法如下:
make a hash as follows
key= each node,
value= all nodes directly accessible from the key node
if a node has no edges it still has a key/value pair in the hash
each edge will be represented twice, once each direction
loop until hash is empty
get any hash key/value pair
save the value to the working-list
remove the key/value from the hash
in a loop until the working-list is empty
(when (gethash (car working-list) hash)
concatenate value to the end of the working-list
(remhash (car working-list) hash))
(pop working-list)
When the loop is finished you have removed all nodes and edges in a single subtree from the hash.
Increment number of subtrees.
end loop until the hash is empty.
report number of subtrees
下面的代码:
(defun count-subtrees (hash)
; hash
; key= each node,
; value= all nodes directly accessible from the key node
; if a node has no edges it still has a key/value pair in the hash
; each edge will be represented twice, once each direction
(let ((number-of-trees 0))
(while (setf key (anykey-in-hash hash)) ; this is where I need any key in the hash
(setf working-list (gethash key hash))
(remhash key hash)
(while (gethash (car working-list) hash)
(setf working-list (append working-list
(gethash (car working-list hash))))
(remhash (car working-list) hash)
(pop working-list))
(incf number-of-trees))
number-of-trees))
我不想遍历键,我想只有一个。
备注:
谢谢大家的回复。我正在将这些评论引导给你。
编辑改变了我的问题,添加了“随机”一词。我不在乎它是否随机。回应:
(defun anykey-in-hash (hash-table)
(block nil
(maphash (lambda (k v) (return (values k v)))
是一个完美的解决方案。
我无意中使用'while'(我从Paul Graham的书中得到)而没有定义它。我希望它不会让任何人感到困惑。
我也用setf代替let来定义变量。愚蠢的错误,我永远不会真的这样做。
最初我有一个所有键的列表。但在算法期间,键/值对被删除。这就是为什么我需要留下任何一个。
我也使用工作列表作为列表。工作列表包含子树中的一些节点。所有这些节点(以及他们的孩子*和他们孩子的孩子......)都需要从哈希中删除。追加到这个列表是为了简化代码。在实际的应用程序中,我会使用其他数据结构,可能是列表的列表。但我觉得这样做会增加复杂性,而不会增加任何问题的含义。
*当我说孩子,我的意思是使用节点作为散列的关键,值是一个孩子的列表。
您正在设置全局变量而未事先声明它们,这是不便携的,并且由于副作用通常不安全;喜欢让绑定。
至于获得“随机”键,你可以简单地实现anykey-in-hash
这样的:
(defun anykey-in-hash (hash-table)
(block nil
(maphash (lambda (k v) (return (values k v)))
hash-table)))
存储在哈希表元素的顺序取决于实施,使maphash
将遍历条目中的任意(但可能是确定性的)订单。如果你真的需要一个随机的顺序,即一个顺序可以改变与不同的函数调用相同的参数,你必须收集的钥匙,并随机选择一个。
在你的例子中,似乎你只需要计算一次键的列表,而不是在while循环的每次迭代中。我亲自得到一个列表中的所有密钥,洗牌它一次,然后流行元素从它的需要。
我原来虽然代码是在Common Lisp中。在CL中,Alexandria library定义了shuffle
(和random-elt
)以及hash-table-keys
(或hash-table-alist
,如果您需要密钥和值)。
在Emacs Lisp中,您也可以使用maphash
轻松实现hash-table-keys
(您可以从maphash调用的函数内部将列表中的按键放在列表的前面)。如果您有Emacs 24.4,您可以(require 'subr-x)
并致电get-hash-keys
。可以像在CL中那样进行混洗,你可以使用亚历山大(https://gitlab.common-lisp.net/alexandria/alexandria/blob/master/sequences.lisp#L90)的算法,知道你只关心参数是列表的情况。
追加到列表的末尾并不是很快,尤其是如果列表很长... –
*我无意中使用了'while'(我从Paul Graham的书中得到)而没有定义它*:我们该怎么做使用标签吗?保持emacs-lisp或更改为common-lisp? – coredump
我不在乎它是否是“Emacs Lisp”。其他人从“Lisp”改变了这个问题 –