问题描述
我已经实现了一种算法来计算最长的连续公共子序列(不要与最长公共子序列混淆，尽管对于这个问题并不重要).我需要从中获得最大的性能，因为我会经常调用它.为了比较性能，我在 Clojure 和 Java 中实现了相同的算法.Java 版本的运行速度明显更快.我的问题是我是否可以对 Clojure 版本做些什么来将其加速到 Java 的水平.
I have implemented an algorithm to calculate the longest contiguous common subsequence (not to be confused with longest common subsequence, though not important for this questions). I need to squeeze maximum performance from this because I'll be calling it a lot. I have implemented the same algorithm in Clojure and Java in order to compare performance. The Java version runs significantly faster. My question is whether there is anything I can do to the Clojure version to speed it up to the level of 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 < a2Len; ++j) {
if (a1[i].equals(a2[j])) {
matchLen = prev[j] + 1; // curr and prev are padded by 1 to allow for this assignment when j=0
}
else {
matchLen = 0;
}
curr[j+1] = matchLen;
if (matchLen > maxLen) {
maxLen = matchLen;
}
}
int[] swap = prev;
prev = curr;
curr = swap;
}
return maxLen;
}
这是相同的 Clojure 版本:
Here is the Clojure version of the same:
(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))))
现在让我们在我的机器上测试这些:
Now let's test these on my machine:
(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 开销".
Clojure is quick but still an order of magnitude slower than Java. Is there anything I can do to close this gap? Or have I maxed it out and one order of magnitude is the "minimal Clojure overhead."
如您所见，我已经在使用循环的低级"构造，我使用的是本机 Java 数组，并且我对参数进行了类型提示以避免反射.
As you can see I am already using the "low level" construct of loop, I am using native Java arrays and I have type-hinted the parameters to avoid reflection.
可能有一些算法优化，但我现在不想去那里.我很好奇我能获得多接近 Java 性能.如果我无法弥补差距，我将只使用 Java 代码.该项目的其余部分在 Clojure 中，但有时为了性能可能需要使用 Java.
There some algorithm optimizations possible, but I don't want to go there right now. I am curious how close to Java performance I can get. If I can't close the gap I'll just go with the Java code. The rest of this project is in Clojure, but perhaps sometimes dropping down to Java for performance is necessary.
推荐答案
在第一个下面添加了一个更快的丑陋版本.
Added a faster uglier version below the first one.
这是我的看法:
(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 与 a[gs]et-int，使用 unchecked- 操作(隐式通过 areduce)，使用向量作为返回值(和交换"机制)和 max-len 在内循环之前被强制为原始值(原始值循环有问题，自 1.5 以来略少)RC2 但支持还不完善，但是 *warn-on-reflection* 不是沉默).
Main differences with yours: a[gs]et vs a[gs]et-int, use of unchecked- ops (implicitly through areduce), use of a vector as the return value (and "swap" mechanism) and max-len is coerced to primitive before the inner loop (primitive-valued loops are problematic, slightly less since 1.5RC2 but the support isn't perfect yet, however *warn-on-reflection* is not silent).
并且我切换到 .equals 而不是 = 以避免 Clojure 等效中的逻辑.
And I switched to .equals instead of = to avoid the logic in Clojure's equiv.
让我们变得丑陋并恢复数组交换技巧:
let's get ugly and restore the arrays swap trick:
(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%.
On my box, it's 30% faster.
这篇关于昂贵算法的 Clojure 性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！