如何在 Clojure 算法实现中处理多个变量？

Question

我是 Clojure 的新手，正在尝试通过在其中实现一些算法来学习。我正在编写的算法用于计算图数据结构的节点 betweenness centrality 指标。

我尝试实现的算法（Brandes 算法）中的函数是这样的：

此处，V 是图的顶点，s 是我们尝试计算的起始节点，return 是最短路径指标 S, Pred and sigma

这是我通过使用 loom 为每个起始节点 start 创建初始图 g 设法得出的结果：

 (defn ss-shortest-path     
   [g start]   
    (let [nodeset (disj (nodes g) start)
        pred (apply assoc {} (interleave (nodes g) (repeat nil)))
        dist (apply assoc {start 0} (interleave nodeset (repeat -1)))
        sigma (apply assoc {start 1} (interleave nodeset (repeat 0)))
        stack []]
    (loop [queue (conj clojure.lang.PersistentQueue/EMPTY start)]
      (if (empty? queue)
        {:sigma sigma
         :pred pred
         :stack stack}
        (let [v (peek queue)
              stack (conj stack v)]
          (doseq [w (successors g v)]
            (when (= (dist w) -1)
              (do
                (conj queue w)
                (assoc dist w (+ 1 (dist v)))))
            (when (= (dist w) (+ 1 (dist v)))
                  (do
                    (assoc sigma w (+ (sigma w) (sigma v)))
                    (assoc pred w v))))
            (recur (pop queue)))))))

我知道 Clojure 数据结构是不可变的，所以每次我在变量 conj 或 assoc 中调用 pred, sigma, stack, dist 时，都会创建一个新副本，而原始变量保持原样.

但是，我不想使用像 atoms、refs 这样的可变状态，因为我有一种感觉，那就是简单地复制我已经知道的命令式风格。

因此，我正在寻求一些经验丰富的 Clojurists 的帮助，以帮助我以惯用的风格创建此功能。

提前致谢。

Answer 1

背景：这里是算法的 java 版本：https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/scoring/BetweennessCentrality.java

首先，您需要定义s、Pred、sigma。您还应该为 g、v、start 等定义格式。

其次，我不确定这是最好的学习练习。您可以将 Java while、for 等替换为 Clojure loop/recur、doseq 等，但感觉仍然像 "force-fit"。通过阅读像 "Clojure for the Brave & True"、"Getting Clojure" 等

这样的好书，你可能会学到更多、更快（而且更深入！）

我们的想法是 self-contained 小练习题比单个庞大的问题更有效地学习。

别忘了收藏：

The Clojure CheatSheet
ClojureDocs.org
clojure-doc.org（是的，尽管名称相似但不同）
The Clojure Cookbook
我的 personal favorite 图书馆 ;)

Answer 2

我会做两件主要的事情：首先，算法有一个由多个"variables"组成的状态（queue，stack， ETC。）。我首先会使用不可变映射构造一个表示算法状态的函数，例如

(defn initialize-state [g start]
  (let [nodeset (disj (nodes g) start)]
    {:g g
     :nodeset nodeset
     :pred (apply assoc {} (interleave (nodes g) (repeat nil)))
     :dist (apply assoc {start 0} (interleave nodeset (repeat -1)))
     :sigma (apply assoc {start 1} (interleave nodeset (repeat 0)))
     :stack []
     :queue (conj clojure.lang.PersistentQueue/EMPTY start)
     :current-vertex nil}))

然后，我会在 REPL 中测试此地图是否针对 g 和 start 的各种选择正确初始化。

Second，我会将算法分解为多个小函数，这些函数将 state 作为输入，returns a state as output，像这样（这段代码不行，需要补缺的部分）：

(defn next-vertex [state]
  {:pre [(state? state)]
   :post [(state? %)]}
  (let [v (peek (:queue state))]
    (-> state
        (update :stack conj v)
        (assoc :current-vertex v))))

(defn process-successor [state w]
  (let [dist-w (dist w)]
    (cond
      ;; fill in...
      )))

(defn process-successors [state]
  {:pre [(state? state)]
   :post [(state? %)]}
  (reduce
   process-successor
   state
   (successors (:g state) (:current-vertex state))))

(defn pop-queue [state]
  {:pre [(state? state)]
   :post [(state? %)]}
  (update state :queue pop))

带有 :pre 和 :post 键的映射是所谓的前置条件和 post 条件，并且 state? 函数可以实现，例如，作为(defn state? [x] (and (map? x) (contains? x :queue)))，就像完整性检查一样。

请注意，对于您编写的每个函数，您可以在编写下一个函数之前在 REPL 中使用一些数据对其进行测试以确保其正常工作。现在可以使用 comp:

将所有这些函数包装到一个完整的状态转换中

(def next-state (comp pop-queue process-successors next-vertex))

现在最终的算法是这样的：

(defn ss-shortest-path [g start]
  (loop [state (initialize-state g start)]
    (if (empty? (:queue state))
      state
      (recur (next-state state)))))

总而言之，如果您将算法分解成更小的部分，可以单独开发和验证，那么实施算法会容易得多。

Answer 3

其他答案都没有明确说明这一点，所以我想我应该清除 "dealing with immutability" 部分。

我会说 loop 是在这里使用的正确结构。您设置的问题是您的循环唯一的累加器是 queue。从一次迭代到下一次迭代变化的每一位数据都应该是循环累加器的一部分。

在您的例子中，dist、sigma、pred 和 stack 都是有可能从一个循环迭代更改为下一个循环迭代的数据，所以它们都应该在循环的方括号中声明。然后，当您需要更新其中一条数据时，您可以更新提供给 recur:

的内容

(loop [queue (conj clojure.lang.PersistentQueue/EMPTY start)
       pred (apply assoc {} (interleave (nodes g) (repeat nil)))
       dist (apply assoc {start 0} (interleave nodeset (repeat -1)))
       sigma (apply assoc {start 1} (interleave nodeset (repeat 0)))
       stack []]

  (if (empty? queue)
    (Return everything)
    (recur (conj queue some-data)
           (assoc pred :some-key some-data)
           (assoc dist :another-key other-data)
           (assoc sigma :key data)
           (conj stack stack-data))))

提供给 recur 的所有内容（在本例中为更新的不可变结构）将在下一次迭代中提供给 loop。

虽然你有这么多累加器，但我同意@Rulle 的观点，将它们全部打包到它们自己的结构中而不是手动处理所有每次迭代要整洁得多。

如何在 Clojure 算法实现中处理多个变量？

How to handle multiple variables in a Clojure algorithm implementation?

algorithm

recursion

functional-programming

clojure

immutability

别忘了收藏：