用于求解动态规划算法的惯用 Clojure

Question

我决定完成 CLRS 算法简介文本，并巧妙地选择了打印问题 此处。

我解决了这个问题，并提出了一个命令式解决方案，该解决方案在 Python 中实现起来很简单，但在 Clojure 中则稍显困难。

我完全无法将计算矩阵函数从我的解决方案转换为惯用的 Clojure。有什么建议吗？以下是计算矩阵函数的伪代码：

// n is the dimension of the square matrix.
// c is the matrix.
function compute-matrix(c, n):
    // Traverse through the left-lower triangular matrix and calculate values.
    for i=2 to n:
        for j=i to n:

            // This is our minimum value sentinal.
            // If we encounter a value lower than this, then we store the new
            // lowest value.
            optimal-cost = INF

            // Index in previous column representing the row we want to point to.
            // Whenever we update 't' with a new lowest value, we need to change
            // 'row' to point to the row we're getting that value from.
            row = 0

            // This iterates through each entry in the previous column.
            // Note: we have a lower triangular matrix, meaning data only
            // exists in the left-lower half.
            // We are on column 'i', but because we're in a left-lower triangular
            // matrix, data doesn't start until row (i-1).
            //
            // Similarly, we go to (j-1) because we can't choose a configuration
            // where the previous column ended on a word who's index is larger
            // than the word index this column starts on - the case which occurs
            // when we go for k=(i-1) to greater than (j-1)
            for k=(i-1) to (j-1):

                // When 'j' is equal to 'n', we are at the last cell and we
                // don't care how much whitespace we have.  Just take the total
                // from the previous cell.
                // Note: if 'j' <  'n', then compute normally.

                if (j < n):
                    z = cost(k + 1, j) + c[i-1, k]

                else:
                    z = c[i-1, k]

                if z < optimal-cost:
                    row = k
                    optimal-cost = z

            c[i,j] = optimal-cost
            c[i,j].row = row

此外，我非常感谢对 Clojure 源代码的其余部分的反馈，特别是关于它的惯用程度。对于迄今为止我编写的 Clojure 代码，我是否能够在命令式范式之外进行充分思考？这里是：

(ns print-neatly)

;-----------------------------------------------------------------------------
; High-order function which returns a function that computes the cost
; for i and j where i is the starting word index and j is the ending word
; index for the word list "word-list."
;
(defn make-cost [word-list max-length]
  (fn [i j]
    (let [total (reduce + (map #(count %1) (subvec word-list i j)))
          result (- max-length (+ (- j i) total))]
      (if (< result 0)
        nil
        (* result result result)))))

;-----------------------------------------------------------------------------
; initialization function for nxn matrix
;
(defn matrix-construct [n cost-func]
  (let [; Prepend nil to our collection.
        append-empty
          (fn [v]
            (cons nil v))

        ; Like append-empty; append cost-func for first column.
        append-cost
          (fn [v, index]
            (cons (cost-func 0 index) v))

        ; Define an internal helper which calls append-empty N times to create
        ; a new vector consisting of N nil values.
        ; ie., [nil[0] nil[1] nil[2] ... nil[N]]
        construct-empty-vec
          (fn [n]
            (loop [cnt n coll ()]
              (if (neg? cnt)
                (vec coll)
                (recur (dec cnt) (append-empty coll)))))

        ; Construct the base level where each entry is the basic cost function
        ; calculated for the base level. (ie., starting and ending at the
        ; same word)
        construct-base
          (fn [n]
            (loop [cnt n coll ()]
              (if (neg? cnt)
                (vec coll)
                (recur (dec cnt) (append-cost coll cnt)))))]

    ; The main matrix-construct logic, which just creates a new Nx1 vector
    ; via construct-empty-vec, then prepends that to coll.
    ; We end up with a vector of N entries where each entry is a Nx1 vector.
    (loop [cnt n coll ()]
      (cond
        (zero? cnt) (vec coll)
        (= cnt 1) (recur (dec cnt) (cons (construct-base n) coll))
        :else (recur (dec cnt) (cons (construct-empty-vec n) coll))))))

;-----------------------------------------------------------------------------
; Return the value at a given index in a matrix.
;
(defn matrix-lookup [matrix row col]
  (nth (nth matrix row) col))

;-----------------------------------------------------------------------------
; Return a new matrix M with M[row,col] = value
; but otherwise M[i,j] = matrix[i,j]
;
(defn matrix-set [matrix row col value]
  (let [my-row (nth matrix row)
        my-cel (assoc my-row col value)]
    (assoc matrix row my-cel)))

;-----------------------------------------------------------------------------
; Print the matrix out in a nicely formatted fashion.
;
(defn matrix-print [matrix]
  (doseq [j (range (count matrix))]
    (doseq [i (range (count matrix))]
      (let [el (nth (nth matrix i) j)]
        (print (format "%1$8.8s" el)))) ; 1st item max 8 and min 8 chars
    (println)))


;-----------------------------------------------------------------------------
; Main
;-----------------------------------------------------------------------------


;-----------------------------------------------------------------------------
; Grab all arguments from the command line.
;
(let [line-length (Integer. (first *command-line-args*))
      words (vec (rest *command-line-args*))
      cost (make-cost words line-length)
      matrix (matrix-construct (count words) cost)]
  (matrix-print matrix))

编辑：我已经根据给出的反馈更新了我的矩阵构造函数，所以现在它实际上比我的 Python 实现短了一行。

;-----------------------------------------------------------------------------
; Initialization function for nxn matrix
;
(defn matrix-construct [n cost-func]
  (letfn [; Build an n-length vector of nil
          (construct-empty-vec [n]
            (vec (repeat n nil)))

          ; Short-cut so we can use 'map' to apply the cost-func to each
          ; element in a range.
          (my-cost [j]
            (cost-func 0 j))

          ; Construct the base level where each entry is the basic cost function
          ; calculated for the base level. (ie., starting and ending at the
          ; same word)
          (construct-base-vec [n]
            (vec (map my-cost (range n))))]

    ; The main matrix-construct logic, which just creates a new Nx1 vector
    ; via construct-empty-vec, then prepends that to coll.
    ; We end up with a vector of N entries where each entry is a Nx1 vector.
    (let [m (repeat (- n 1) (construct-empty-vec n))]
      (vec (cons (construct-base-vec n) m)))))

Answer 1

1. 不要使用带有 fn 的 let，而是尝试 letfn。
2. 剂量q 剂量q -> 可能会更好
3. 看起来作为理解你的条件/零 ？ / = 1 带有大小写的代码会更容易阅读（并且更快）。
4. 我的蜘蛛感告诉我，这里的循环/递归应该是某种映射调用，而不是
5. 我强烈怀疑这对于原始数组来说会更快（并且在某些地方可能更干净）
6. 您可能想使用或查看源代码对于Incanter

Answer 2

我爬上了墙，能够以一种足够类似于 Clojure 的方式思考，将核心计算矩阵算法转化为可行的程序。

它只比我的 Python 实现长一行，尽管它看起来写得更密集。当然，像“map”和“reduce”这样的概念是更高级别的函数，需要您充分思考。

我相信这个实现也修复了我的 Python 中的一个错误。 :)

;-----------------------------------------------------------------------------
; Compute all table entries so we can compute the optimal cost path and
; reconstruct an optimal solution.
;
(defn compute-matrix [m cost]
  (letfn [; Return a function that computes 'cost(k+1,j) + c[i-1,k]'
          ; OR just 'c[i-1,k]' if we're on the last row.
          (make-min-func [matrix i j]
            (if (< j (- (count matrix) 1))
              (fn [k]
                (+ (cost (+ k 1) j) (get-in matrix [(- i 1) k])))
              (fn [k]
                (get-in matrix [(- i 1) k]))))

          ; Find the minimum cost for the new cost: 'cost(k+1,j)'
          ; added to the previous entry's cost: 'c[i-1,k]'
          (min-cost [matrix i j]
            (let [this-cost (make-min-func matrix i j)
                  rang (range (- i 1) (- j 1))
                  cnt (if (= rang ()) (list (- i 1)) rang)]
              (apply min (map this-cost cnt))))

          ; Takes a matrix and indices, returns an updated matrix.
          (combine [matrix indices]
            (let [i (first indices)
                  j (nth indices 1)
                  opt (min-cost matrix i j)]
              (assoc-in matrix [i j] opt)))]

    (reduce combine m
        (for [i (range 1 (count m)) j (range i (count m))] [i j]))))

谢谢亚历克斯和杰克的评论。他们都非常有帮助，帮助我走向了惯用的 Clojure。

Answer 3

我在 Clojure 中处理动态程序的一般方法不是直接搞乱值矩阵的构造，而是将记忆与定点组合器结合使用。这是我计算编辑距离的示例：

(defn edit-distance-fp
  "Computes the edit distance between two collections"
  [fp coll1 coll2]
  (cond
      (and (empty? coll1) (empty? coll2)) 0
      (empty? coll2) (count coll1)
      (empty? coll1) (count coll2)
      :else (let [x1 (first coll1)
                  xs (rest coll1)
                  y1 (first coll2)
                  ys (rest coll2)]
                 (min
                  (+ (fp fp xs ys) (if (= x1 y1) 0 1))
                  (inc (fp fp coll1 ys))
                  (inc (fp fp xs coll2))))))

与这里的朴素递归解决方案的唯一区别是简单地将递归调用替换为对 fp 的调用。

然后我用以下命令创建一个记忆固定点：

(defn memoize-recursive [f] (let [g (memoize f)] (partial g g)))

(defn mk-edit-distance [] (memoize-recursive edit-distance-fp))

然后用以下命令调用它：

> (time ((mk-edit-distance) 
  "the quick brown fox jumped over the tawdry moon" 
  "quickly brown foxes moonjumped the tawdriness"))
"Elapsed time: 45.758 msecs"
23

我发现记忆比变异表更容易让我思考。

Answer 4

您的矩阵查找和矩阵集函数可以得到简化。您可以使用 assoc-in 和 get-in 来操作嵌套关联结构。

(defn matrix-lookup [matrix row col]
 (get-in matrix [row col]))

(defn matrix-set [matrix row col value]
  (assoc-in matrix [row col] value))

Alex Miller 提到使用原始数组。如果您最终需要朝这个方向发展，您可以首先查看 int-array、aset-int 和 aget。请参阅 clojure.core 文档以了解更多信息。