k-dツリー内のアイテムを検索する

Question

私はLispでk-dツリーを開発しています。私は、k-dツリーのノードを検索できるようにする関数を書いています。 '((2 3) (5 4) (9 6) (4 7) (8 1) (7 2))：私は、以下のデータをツリーを構築

(defmethod find-node ((kdt kdtree) target &key (key #'value) (test #'equal)) 
    (unless (null (root kdt)) 
    (find-node (root kdt) target :key key :test test))) 

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal)) 
    (format t "Testing node ~a~%" (value node)) 
    (format t "Result is ~a~%" (funcall test (funcall key node) target)) 
    (if (funcall test (funcall key node) target) 
     node 
     (progn 
     (unless (null (left node)) 
      (find-node (left node) target :key key :test test)) 
     (unless (null (right node)) 
      (find-node (right node) target :key key :test test))))) 

次のようにこの関数が定義されます。だから今、私はノード'(2 3)を見つけるためにこの関数を使用しています。 format文で

(find-node kdt '(2 3)) 

、私はこの出力を得る：だから

Testing node (7 2) 
Result is NIL 
Testing node (5 4) 
Result is NIL 
Testing node (2 3) 
Result is T 
Testing node (4 7) 
Result is NIL 
Testing node (9 6) 
Result is NIL 
Testing node (8 1) 
Result is NIL 
NIL 

、テストの結果がTあるので、あなたが見ることができるように、ノードが発見された、しかし、検索が続行され、結果はNILです。なぜこの関数はノードを返さないのですか？

Answer 1

あなたが何かを見つけたときに、直接、結果を返すようにしたいかもしれません。これを解決する1つの方法は、このような関数を書き換えることです。

あなたのコードを改善するために、次の例を使用します。

(defun find-it (item list) 
    (labels ((find-it-aux (item list) 
      (when list 
       (if (eql item (first list)) 
        (return-from find-it (first list)) 
       (find-it-aux item (rest list)))))) 
    (find-it-aux item list))) 

CL-USER 89 > (find-it 1 '(2 3 1 5)) 
1 

CL-USER 90 > (find-it 1 '(2 3 5)) 
NIL 

または

(defun find-it (item list) 
    (catch 'found-it 
    (find-it-aux item list))) 

(defun find-it-aux (item list) 
    (when list 
    (if (eql item (first list)) 
     (throw 'found-it (first list)) 
     (find-it-aux item (rest list))))) 


CL-USER 91 > (find-it 1 '(2 3 1 5)) 
1 

CL-USER 92 > (find-it 1 '(2 3 5)) 
NIL 

Answer 2

この関数は再帰的であるため、ノードをテストし続けます。左に降りる場合は（find-node (left node) ...）、右の枝で検索するよりもスタックに載せます（find-node (right node) ...）。したがって、テスト対象のノードはすべて再帰のためです。

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal)) 
    (let ((left (unless (null (left node)) 
       (find-node (left node) target :key key :test test))) 
     (right (unless (null (right node)) 
       (find-node (right node) target :key key :test test))) 
     (this (funcall test (funcall key node) target))) 
    (if this 
     node 
     (if left 
      left 
      right)))) 

Answer 3

あなたは物事を少し簡素化し、あなたがアイテムを見つけたらnilための方法を定義することで、検索を停止することができますノードと使用：or：

(defmethod find-node ((empty null) target &key &allow-other-keys) 
    nil) 

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal)) 
    (if (funcall test (funcall key node) target) 
     node 
     (or (find-node (left node) target :key key :test test) 
      (find-node (right node) target :key key :test test)))) 

もちろんこれをRainer Joswigの答えと組み合わせてください。たとえば、kdnodeため:around方法を定義することができます：あなたはまた、コード内で明示的にcatchブロックを置くことができ

(defvar *searching* nil) 

(defmethod find-node :around ((x kdnode) target &key &allow-other-keys) 
    (if *searching* 
     (let ((result (call-next-method))) 
     (when result 
      (throw 'found result))) 
     (let ((*searching* t)) 
     (catch 'found 
      (call-next-method))))) 

。 kdnodeで検索を開始することは絶対できませんが、常にkdtreeインスタンスの場合はkdtreeの周りにcatchを置き換えて、特殊変数*searching*を取り除くことができます。

この例は、方法を示すためのものです。それはコードを少し「賢明すぎる」ものにします。おそらく実際にはthrow/catchの振る舞いを明示的に実装するでしょう。