用於解決動態規劃算法的習慣Clojure

Question

我決定通過CLRS Introduction to Algorithms文本工作，並挑選了整齊的問題here。

我解決了這個問題，並提出了一個可以直接在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鍵在它讓，儘量letfn。
2. doseq doseq - >貌似它可能會更好理解
3. 您的cond/zero？/= 1代碼會更容易閱讀（並且更快）。
4. 我的蜘蛛俠，常識告訴我，循環/這裏再次出現應該是某種地圖調用，而不是
5. 我強烈懷疑，這將是（在一些地方和可能的清潔劑）與原始陣列遠快
6. 你可能想使用或查看源代碼Incanter

Answer 2

您的矩陣查找和矩陣集函數可以被簡化。您可以使用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)) 

亞歷克斯米勒提到使用原始數組。如果您最終需要朝這個方向發展，您可以先看看int-array,aset-int和aget。查看clojure.core文檔瞭解更多信息。

Answer 3

我爬上了牆，並能夠以充分的Clojure的方式思考將核心計算矩陣算法轉化爲可行的程序。

這只是比我的Python實現更長的一行，儘管它看起來更密集。當然，像'地圖'和'減少'這樣的概念是更高層次的功能，需要你思考上限。

我相信這個實現也修復了我的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 4

我在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遞歸調用。

然後我創建一個memoized固定點：

(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 

我發現記憶化更容易繞到我的大腦比變異表。