搜索k-d树中的项目

Question

我正在Lisp中开发k-d树。我正在写一个函数，允许我在k-d树中搜索一个节点。该函数定义如下：

(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) (5 4) (9 6) (4 7) (8 1) (7 2))。所以现在，我正在使用这个功能找到节点'(2 3)。

(find-node kdt '(2 3)) 

随着format报表，我得到这样的输出：

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

您可能要直接返回结果，当你找到的东西。

使用下面的例子来提高代码：

(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的答案结合起来。例如，你可以定义一个:around方法kdnode：

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

你也可以明确地放置catch块中的代码。如果您确定永远不会在kdnode上启动搜索，但始终在kdtree实例上，则可以将catch改为kdtree左右，并取消特殊变量*searching*。

请注意，此示例仅用于演示方法。它使代码有点“太聪明”;我可能会在实践中明确实施throw/catch行为。