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