昂贵算法的Clojure性能

我已经实现了一个算法来计算最长的连续公共子序列（不要与最长的公共子序列混淆，尽管这个问题不重要）。 我需要从中挤出最大的性能，因为我会调用它。 我在Clojure和Java中实现了相同的算法，以便比较性能。 Java版本运行得更快。 我的问题是我是否可以对Clojure版本做任何事情来加速它达到Java的水平。

这是Java代码：

public static int lcs(String[] a1, String[] a2) { if (a1 == null || a2 == null) { return 0; } int matchLen = 0; int maxLen = 0; int a1Len = a1.length; int a2Len = a2.length; int[] prev = new int[a2Len + 1]; // holds data from previous iteration of inner for loop int[] curr = new int[a2Len + 1]; // used for the 'current' iteration of inner for loop for (int i = 0; i < a1Len; ++i) { for (int j = 0; j  maxLen) { maxLen = matchLen; } } int[] swap = prev; prev = curr; curr = swap; } return maxLen; } 

这是相同的Clojure版本：

 (defn lcs [#^"[Ljava.lang.String;" a1 #^"[Ljava.lang.String;" a2] (let [a1-len (alength a1) a2-len (alength a2) prev (int-array (inc a2-len)) curr (int-array (inc a2-len))] (loop [i 0 max-len 0 prev prev curr curr] (if (< i a1-len) (recur (inc i) (loop [j 0 max-len max-len] (if (< j a2-len) (if (= (aget a1 i) (aget a2 j)) (let [match-len (inc (aget prev j))] (do (aset-int curr (inc j) match-len) (recur (inc j) (max max-len match-len)))) (do (aset-int curr (inc j) 0) (recur (inc j) max-len))) max-len)) curr prev) max-len)))) 

现在让我们在我的机器上测试这些：

 (def pool "ABC") (defn get-random-id [n] (apply str (repeatedly n #(rand-nth pool)))) (def a1 (into-array (take 10000 (repeatedly #(get-random-id 5))))) (def a2 (into-array (take 10000 (repeatedly #(get-random-id 5))))) 

Java的：

 (time (Ratcliff/lcs a1 a2)) "Elapsed time: 1521.455 msecs" 

Clojure的：

 (time (lcs a1 a2)) "Elapsed time: 19863.633 msecs" 

Clojure很快，但仍然比Java慢一个数量级。 有什么办法可以缩小这个差距吗？ 或者我将它最大化，一个数量级是“最小的Clojure开销”。

正如您所看到的，我已经在使用循环的“低级”构造，我使用的是本机Java数组，并且我已经使用类型提示参数来避免reflection。

有一些算法优化可能，但我现在不想去那里。 我很好奇我能获得的Java性能有多接近。 如果我无法缩小差距，我将使用Java代码。 这个项目的其余部分是在Clojure中，但有时可能需要降低Java性能。

Answer 1

编辑：在第一个下面添加了一个更快的丑陋版本。

这是我的看法：

 (defn my-lcs [^objects a1 ^objects a2] (first (let [n (inc (alength a1))] (areduce a1 i [max-len ^ints prev ^ints curr] [0 (int-array n) (int-array n)] [(areduce a2 j max-len (unchecked-long max-len) (let [match-len (if (.equals (aget a1 i) (aget a2 j)) (unchecked-inc (aget prev j)) 0)] (aset curr (unchecked-inc j) match-len) (if (> match-len max-len) match-len max-len))) curr prev])))) 

与你的主要区别： a[gs]et vs a[gs]et-int ，使用unchecked- ops（隐式地通过areduce ），使用向量作为返回值（和“swap”机制）和max-len是在内循环之前强制转换为原语（原始值循环是有问题的，自1.5RC2以来稍微少一些但是支持还不完美，但*warn-on-reflection*不是静默的）。

我切换到.equals而不是=来避免Clojure中的逻辑.equals 。

编辑：让我们变得丑陋并恢复数组交换技巧：

 (deftype F [^:unsynchronized-mutable ^ints curr ^:unsynchronized-mutable ^ints prev] clojure.lang.IFn (invoke [_ a1 a2] (let [^objects a1 a1 ^objects a2 a2] (areduce a1 i max-len 0 (let [m (areduce a2 j max-len (unchecked-long max-len) (let [match-len (if (.equals (aget a1 i) (aget a2 j)) (unchecked-inc (aget prev j)) 0)] (aset curr (unchecked-inc j) (unchecked-int match-len)) (if (> match-len max-len) match-len max-len))) bak curr] (set! curr prev) (set! prev bak) m))))) (defn my-lcs2 [^objects a1 a2] (let [n (inc (alength a1)) f (F. (int-array n) (int-array n))] (f a1 a2))) 

在我的盒子上，它快了30％。

Answer 2

以下是一些改进：

1. 花式类型提示没有优势，只需使用^对象
2. 我认为aset-int已被弃用 – 只是简单的旧版本更快，总体看起来大约是3倍

除此之外（以及上面提到的复发的长型提示），我没有看到任何明显的进一步改进的方法。

 (defn lcs [^objects a1 ^objects a2] (let [a1-len (alength a1) a2-len (alength a2) prev (int-array (inc a2-len)) curr (int-array (inc a2-len))] (loop [i 0 max-len 0 prev prev curr curr] (if (< i a1-len) (recur (inc i) (long (loop [j 0 max-len max-len] (if (< j a2-len) (if (= (aget a1 i) (aget a2 j)) (let [match-len (inc (aget prev j))] (do (aset curr (inc j) match-len) (recur (inc j) (max max-len match-len)))) (do (aset curr (inc j) 0) (recur (inc j) max-len))) max-len))) curr prev) max-len)))) #'user/lcs user> (time (lcs a1 a2)) "Elapsed time: 3862.211 msecs"