Поиск элемента в дереве k-d

Question

Я разрабатываю дерево k-d в Lisp. Я пишу функцию, которая позволяет мне искать узел в дереве 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)))) 

Вы можете Объедините это с ответом Райнера Йосвига, конечно. Например, вы можете определить :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 явно на практике.