0

考虑一个像这样的图，由节点和邻居组成：

(defparameter *graph* '((A (B C D))
                        (B (A C E))
                        (C (A B D E))
                        (D (A C E))
                        (E (B C D))))

...以及每个节点的一组标签：

(defparameter *values* '((A 1)
                         (B 2)
                         (C 3)
                         (D 2)
                         (E 1)))

我正在尝试编写一个函数来评估该格式的图形并确定相邻节点是否具有相同的标签。如果我是用 C++ 或 Java 编写的，我的函数迭代版本的逻辑可能如下所示：

(defun evaluate-label (graph values)
;; for every node in graph
  ;; for every adjoining node
    ;; if (node.value == adjoiningNode.value)
      ;; return false
;; return true
)

...但我不确定哪种逻辑更适合 Lisp，更不用说如何进行编码了。

所以，两个问题：

  1. 这个函数的“Lispy”伪代码会是什么样子？
  2. 您会在函数中添加哪些特定的语法特征？我们假设有一个cond. every对这个问题有用吗？我们可以在不使用 lambda 表达式的情况下轻松做到这一点吗？

提前感谢您的任何反馈！

4

1 回答 1

3

无论使用何种语言，良好编程的一个重要方面是良好的抽象。有时，这可能是个人喜好问题，但这里有一个尝试对这个问题应用一些抽象的示例。一旦你有了你的图表和你的值，你就可以定义一个节点值函数来返回一个节点的值。然后你可以将你的问题表述为

图中是否有某个节点与其邻居之一具有相同的节点值？

用some写起来并不难：

(defun adjacent-values-p (graph values)
  (flet ((node-value (node)
           (cadr (assoc node values))))
    (some #'(lambda (node-descriptor)
              (destructuring-bind (node neighbors)
                  node-descriptor
                (find (node-value node) neighbors
                      :key #'node-value)))
          graph)))


(adjacent-values-p '((a (b c)))
                   '((a 1) (b 2) (c 1)))
;=> C

(adjacent-values-p '((a (b c)))
                   '((a 1) (b 2) (c 3)))
;=> NIL

也就是说，即使这在某些意义上可能更像 Lisp-y，但使用带有dolist的显式迭代来编写它可能同样有意义：

(defun adjacent-values-p (graph values)
  (flet ((node-value (node)
           (cadr (assoc node values))))
    (dolist (node-descriptor graph)
      (destructuring-bind (node neighbors) node-descriptor
        (when (member (node-value node) neighbors :key #'node-value)
          (return t))))))

使用loop会更好，它支持一些解构：

(defun adjacent-values-p (graph values)
  (flet ((node-value (node)
           (cadr (assoc node values))))
    (loop for (node neighbors) in graph
       thereis (find (node-value node) neighbors :key #'node-value))))

所有这些版本都可以受益于将值存储在，例如。用于更快检索的哈希表。在这里这样做是否有意义取决于您的需求、应用程序域等。否则，您将检索边缘标签 O(2×|E|)，每次都进行 O(|V|) 遍历。例如：

(let ((table (make-hash-table)))
  (flet ((node-value (node)
           (multiple-value-bind (value presentp)
               (gethash node table)
             (if presentp value
                 (setf (gethash node table)
                       (cadr (assoc node values)))))))
    ;; ...
    ))

通过在需要之前不查找节点值来“按需”缓存。但是，由于应该需要每个节点值（假设提供的值列表不包含任何额外的节点），因此最好在开始时填充表。然后你以后不必做任何检查，你只需要遍历值列表一次。因此：

(defun adjacent-values-p (graph values &aux (table (make-hash-table)))
  (loop for (node value) in values
     doing (setf (gethash node table) value))
  (flet ((node-value (node)
           (gethash node table)))
    ;; ...
    ))
于 2014-09-29T03:12:51.567 回答