java - 高価なアルゴリズムに対するClojureのパフォーマンス

Question

最長連続共通サブシーケンスを計算するアルゴリズムを実装しました(最長共通サブシーケンスと混同しないでください。ただし、この質問には重要ではありません)。何度も呼び出すので、ここから最大のパフォーマンスを絞り出す必要があります。パフォーマンスを比較するために、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 < 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 バージョンです。

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

ジャワ:

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

クロージャ:

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

Clojure は高速ですが、それでも Java よりも 1 桁遅いです。このギャップを埋めるために私にできることはありますか? または、私はそれを最大限に活用しましたが、1 桁は「最小限の Clojure オーバーヘッド」です。

ご覧のとおり、ループの「低レベル」構造を既に使用しており、ネイティブ Java 配列を使用しており、リフレクションを避けるためにパラメーターに型ヒントを付けています。

いくつかのアルゴリズムの最適化が可能ですが、今はそこに行きたくありません。Java のパフォーマンスにどれだけ近づくことができるか興味があります。ギャップを埋めることができない場合は、Java コードを使用します。このプロジェクトの残りの部分は Clojure にありますが、パフォーマンスのために Java に落とし込む必要がある場合もあります。

score 13 · Accepted Answer

編集:最初のものの下に、より高速で醜いバージョンを追加しました。

これが私の見解です：

(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]etvs a[gs]et-int、unchecked-ops の使用 (暗黙的にを介してareduce)、戻り値としてのベクトルの使用 (および「スワップ」メカニズム)、および max-len は内側のループの前にプリミティブに強制されます (プリミティブ値のループは問題があります。 1.5RC2 からわずかに減少しましたが、サポートはまだ完全ではありませんが、*warn-on-reflection*サイレントではありません)。

そして、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% 高速です。

score 6 · Accepted Answer

Here are a couple improvements:

No advantage to fancy type hinting, just use ^objects
aset-int is deprecated I believe -- just plain old aget is faster, by about 3x overall it seems

Beyond that (and the long type hint on the recur mentioned above), I don't see any obvious ways to improve further.

(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"

java - 高価なアルゴリズムに対するClojureのパフォーマンス

2 に答える 2

Related

Reference