用于求解动态规划算法的习服

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

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

;-----------------------------------------------------------------------------
; 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. 与其在其中使用let和fn，不如尝试letfn。
2. doseq ->看上去可能更适合理解
3. 您的cond / zero? /=1代码使用大小写将更容易阅读(而且更快)。
4. 我的感觉告诉我，这里的循环/递归应该是某种映射调用。
5. 我强烈怀疑，使用原始数组(在某些地方可能更干净)，这会快得多。
6. 您可能希望使用或查看领队的源代码

Answer 2

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

它只比我的Python实现长一行，尽管它似乎编写得更密集。当然，“映射”和“减少”这样的概念是更高层次的函数，需要你把你的思维上限。

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

;-----------------------------------------------------------------------------
; 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

我发现回忆录比变桌子更容易让我头脑清醒。