Emacs Lispでは、どのようにして1つのハッシュキーを取得しますか？

Question

私が解決しようとしている問題は、各ノードがサブツリーにある非有向グラフで、最も少ない数のサブツリーを見つけることです。

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

私はキーを反復処理する必要はありませんが、私は1を取得したい

私のアルゴリズムは次のようです。

注：

ありがとうございます。私はあなたにこれらのコメントを指示しています。

エディタが私の質問を変更し、「ランダムに」という言葉を追加しました。ランダムであるかどうかは気にしない。応答：

(defun anykey-in-hash (hash-table) 
    (block nil 
     (maphash (lambda (k v) (return (values k v))) 

は完璧な解決策です。

「私はポール・グラハムの本から得たもの」を間違いなく定義していませんでした。私は誰もそれを混乱させないことを願っています。

また、letの代わりにsetfを使って変数を定義しました。愚かな間違い、私は本当にそれを行うことはありません。

最初はすべてのキーのリストがあります。しかしアルゴリズムの間に、キーと値のペアは削除されます。だからこそ私は誰かを残す必要があるのです。

私もリストとしてワーキングリストを使用しています。作業リストには、サブツリー内のいくつかのノードが含まれています。これらのノード（およびその子*およびその子の子供...）のすべてをハッシュから削除する必要があります。このリストに追加することは、コードを簡素化することでした。実際のアプリケーションでは、他のデータ構造、おそらくリストのリストを使用します。しかし、ここでそうすることは、質問の意味に何も追加せずに複雑さを増すことになると感じました。

*私が子供と言うとき、私はハッシュのキーとしてノードを使うことを意味します、値は子供のリストです。

Answer 1

グローバル変数は、事前に宣言することなく設定しています。これは移植性が低く、副作用のために一般的に安全ではありません。バインディングを優先させる。 「ランダム」のキーを取得するためとして

、あなたは、単にこのようanykey-in-hashを実装することができます

(defun anykey-in-hash (hash-table) 
    (block nil 
    (maphash (lambda (k v) (return (values k v))) 
      hash-table))) 

ハッシュテーブルに格納されている要素の順序は実装に依存するため、maphashは、任意のエントリを反復します（しかし、おそらく確定的な）順序である。 ランダムの順序が必要な場合、つまり、同じ引数を使用して異なる関数呼び出しで変更できる順序の場合は、キーを収集してランダムに選択する必要があります。

例では、whileループの繰り返しごとにではなく、キーのリストを1回だけ計算する必要があるようです。私は個人的にリスト内のすべてのキーを取得したいと考えています。シャッフルそれを一度、次にpop要素を必要に応じて入れます。

私はもともとコードはCommon Lispにありましたが、CLの場合、Alexandria libraryはshuffle（およびrandom-elt）、hash-table-keys（またはキーと値の両方が必要な場合はhash-table-alist）を定義します。

hash-table-keysをmaphashで簡単に実装できます（maphash関数の中からリストの前にキーを押します）。 Emacs 24.4をお持ちの場合は(require 'subr-x)となり、get-hash-keysとなります。シャッフルはCLのように行うことができます。アレキサンドリア（https://gitlab.common-lisp.net/alexandria/alexandria/blob/master/sequences.lisp#L90）からアルゴリズムを適用することができます。引数がリストである場合のみに注意してください。