在Clojure的條件表達式中保存重複計算？

Question

在下面的代碼中，我需要計算鍵盤和驅動器中一個元素的總和的最大值，其總和應小於或等於s。

(def s 10) 
    (def keyboards '(3 1)) 
    (def drives '(5 2 8)) 

    (let [k (sort (fn [x y] (> x y)) keyboards) ; sort into decreasing 
     d (sort (fn [x y] (> x y)) drives) ; sort into decreasing 
     ] 
    (loop [k1 (first k) ks (rest k) d1 (first d) ds (rest d)] 
     (cond 
     (or (nil? k1) (nil? d1)) -1  ; when one of the list is empty 
     (< (+ k1 d1) s) (+ k1 d1)  ; whether (+ k1 d1) can be saved to compute once? 
     (and (empty? ks) (empty? ds)) -1 
     (empty? ks) (if (< (+ k1 (first ds)) s) (+ k1 (first ds)) -1) ; whether (+ k1 (first ds)) can be saved once? 
     (empty? ds) (if (< (+ d1 (first ks)) s) (+ d1 (first ks)) -1) ; whether (+ d1 (first ks)) can be saved once? 
     :else (let [bs (take-while #(< % s) [ (+ k1 (first ds)) (+ (first ks) d1) ])] 
       (if (empty? bs) (recur (first ks) (rest ks) (first ds) (rest ds)) 
        (apply max bs)))))) 

正如評論所示，我想知道是否有任何方法可以進一步優化條件表達式中的重複添加操作。 在條件檢查之前使用let綁定來計算它們可能並不是最優的，因爲只有一個條件是真的，因此其他條件的計算將被浪費。

我不知道Clojure編譯器是否足夠聰明，可以爲我優化重複計算，還是有一個巧妙的表達式使得在檢查和返回值中只執行一次操作？

任何建議，使代碼更習慣性將不勝感激。

Answer 1

如果你想保持當前的代碼的結構，可以用馬克英格better-cond庫：

(require '[better-cond.core :as b]) 

(def s 10) 
(def keyboards '(3 1)) 
(def drives '(5 2 8)) 

(let [k (sort (fn [x y] (> x y)) keyboards) ; sort into decreasing 
     d (sort (fn [x y] (> x y)) drives)] ; sort into decreasing 
    (loop [k1 (first k) ks (rest k) d1 (first d) ds (rest d)] 
    (b/cond 
     (or (nil? k1) (nil? d1)) -1   ; when one of the list is empty 
     :let [x (+ k1 d1)] 
     (< x s) x 
     (and (empty? ks) (empty? ds)) -1 
     :let [y (+ k1 (first ds))] 
     (empty? ks) (if (< y s) (dec y)) 
     :let [z (+ d1 (first ks))] 
     (empty? ds) (if (< z s) (dec z)) 
     :else (let [bs (take-while #(< % s) [(+ k1 (first ds)) (+ (first ks) d1)])] 
       (if (empty? bs) (recur (first ks) (rest ks) (first ds) (rest ds)) 
       (apply max bs)))))) 

Answer 2

這聽起來有點像的knapsack problem。計算它的計算效率更高，但如果您處理的是少於幾百個的兩個或三個小列表，並且它不是在熱循環中運行的關鍵代碼片段，請考慮多簡單：

(let [upper-limit 10 
     keyboards [3 1] 
     drives [5 2 8]] 

    (apply max 
     (for [k keyboards 
       d drives 
       :let [sum (+ k d)] 
       :when (<= sum upper-limit)] 
      sum))) 

你執行你的（潛在的昂貴）計算一次（在:let結合），這是你真正在問什麼。這是O(n^2)，但如果它符合上述標準，這是一個解決方案，可以容易地被讀者理解;因此它是可維護的。如果它儘可能高效至關重要，請考慮更具算法效率的解決方案。

由昱伸編輯：

有一個小問題時，有沒有符合條件的總和。它可能會改進如下：

(let [upper-limit 10 
     keyboards [3 1] 
     drives [5 2 8] 
     eligbles (for [k keyboards 
        d drives 
        :let [sum (+ k d)] 
        :when (<= sum upper-limit)] 
       sum)] 
    (if (empty? eligbles) 
    nil 
    (apply max eligbles)))