clojure - clojure中的最大子数组算法

Question

kanade 的算法解决了 maximum subarray problem .我正在尝试学习 clojure，所以我想到了这个实现:

(defn max-subarray [xs]
  (last
    (reduce
      (fn [[here sofar] x]
        (let [new-here (max 0 (+ here x))]
          [new-here (max new-here sofar)]))
      [0 0]
      xs)))

这看起来真的很冗长。 有没有更简洁的方法在 clojure 中实现这个算法？

Answer 1

正如我在对该问题的评论中所说，我相信 OP 的方法是最佳的。这给出了一个完全通用的问题，其中输入是任意数字的可序列。

但是，如果添加的要求是输入应该是 long 的集合(或 double ；其他原语也可以，只要我们不将整数与 float 混合)，循环/recur 通过利用原始算法，可以使基于解决方案的速度显着加快:

(defn max-subarray-prim [xs]
  (loop [xs (seq xs) here 0 so-far 0]
    (if xs
      (let [x (long (first xs))
            new-here (max 0 (+ here x))]
        (recur (next xs) new-here (max new-here so-far)))
      so-far)))

虽然我更喜欢 reduce，但在没有特别理由使用 loop/recur 的情况下，这实际上对我来说非常可读。现在的希望是 loop 在整个循环执行过程中保持 here 和 so-far 未装箱的能力将产生足够的差异性能 -明智的。

为了对此进行基准测试，我生成了一个包含 100000 个随机整数的向量，范围为 -50000，...，49999:

(def xs (vec (repeatedly 100000 #(- (rand-int 100000) 50000))))

完整性检查(max-subarray-orig 指的是 OP 的实现):

(= (max-subarray-orig xs) (max-subarray-prim xs))
;= true

Criterium 基准:

(do (c/bench (max-subarray-orig xs))
    (flush)
    (c/bench (max-subarray-prim xs)))
WARNING: Final GC required 3.8238570080506156 % of runtime
Evaluation count : 11460 in 60 samples of 191 calls.
             Execution time mean : 5.295551 ms
    Execution time std-deviation : 97.329399 µs
   Execution time lower quantile : 5.106146 ms ( 2.5%)
   Execution time upper quantile : 5.456003 ms (97.5%)
                   Overhead used : 2.038603 ns
Evaluation count : 28560 in 60 samples of 476 calls.
             Execution time mean : 2.121256 ms
    Execution time std-deviation : 42.014943 µs
   Execution time lower quantile : 2.045558 ms ( 2.5%)
   Execution time upper quantile : 2.206587 ms (97.5%)
                   Overhead used : 2.038603 ns

Found 5 outliers in 60 samples (8.3333 %)
    low-severe   1 (1.6667 %)
    low-mild     4 (6.6667 %)
 Variance from outliers : 7.8724 % Variance is slightly inflated by outliers

因此每次调用从 ~5.29 毫秒跃升至 ~2.12 毫秒。