8
Tôi quyết định làm việc thông qua văn bản Giới thiệu về thuật toán CLRS và chọn vấn đề in gọn gàng here.Clojure lập trình để giải quyết thuật toán lập trình động
Tôi đã khắc phục sự cố và đưa ra một giải pháp bắt buộc đơn giản để triển khai bằng Python, nhưng hơi kém trong Clojure.
Tôi hoàn toàn bối rối khi dịch hàm ma trận tính toán từ giải pháp của tôi thành Clojure thành ngữ. Bất kỳ đề xuất? Dưới đây là mã giả cho hàm tính toán ma trận:
// 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
Ngoài ra, tôi sẽ rất nhiều đánh giá cao phản hồi về phần còn lại của nguồn Clojure của tôi, đặc biệt là liên quan đến cách thành ngữ nó được. Tôi đã cố gắng suy nghĩ đầy đủ bên ngoài mô hình mệnh lệnh cho mã Clojure tôi đã viết cho đến nay chưa? Ở đây là:
(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))
EDIT: Tôi đã cập nhật chức năng ma trận-xây dựng của tôi với các thông tin phản hồi nhất định, vì vậy bây giờ nó thực sự là một dòng ngắn hơn so với thực hiện Python của tôi.
;-----------------------------------------------------------------------------
; 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)))))
1. Đề xuất tuyệt vời. Tôi không biết có một thứ như letfn. 2. Tôi đã cố gắng để hiểu được việc xây dựng ma trận sử dụng liều lượngq. Hy vọng rằng có nhiều đề xuất hơn cho các ví dụ thực tế? :) 4. Tôi đã sử dụng một số bản đồ, nhưng vết thương bằng cách sử dụng '_' để bỏ qua một số giá trị và nghĩ rằng đó là "không tinh khiết", vì thiếu một từ tốt hơn. Nó có thể là thành ngữ hơn, mặc dù, như tôi đã nhìn thấy nó trong một số ví dụ gần đây. 5. Bạn có ý nghĩa gì bởi 'mảng nguyên thủy'? Cảm ơn phản hồi! (câu trả lời được rút gọn để phù hợp với các ràng buộc về nhận xét) – GrooveStomp