二項係数の成長可能な配列のためのダブルチェックロック

Question

二重チェックロックを使用して、一連の二項係数を維持しようとしていますが、最近、ダブルチェックロックが機能しないことを読みました。効率は非常に重要であるため、条件のステートメントの内側のみでない限り、揮発性を使用することはオプションではありません。 Singletonオブジェクトを使用して静的クラスを使用する方法がわかりません（これはフレームワークの一部であり、人々が機能を使用する必要がある数字の種類がわかりません。選択された値は、関数がまったく使用されるかどうかです）。私が考えることができる唯一のことは、すべてを静的ではないようにし、この方法を使用する必要がある各スレッドが独自の配列を使用して選択オブジェクトをインスタンス化することを主張することです。それは必要ではないようです。

public static final class Util{
/**
 * Static array of nCr values
 */
public static long[][] nCr_arr;

/**
 * Calculate binomial coefficient (n k)
 * 
 * @param n
 *            n
 * @param k
 *            k
 * @return n choose k
 */
public static long nCr(int n, int k) {
    if (k < 0)
        throw new ArithmeticException("Cannot choose a negative number");
    if (n < 0) {
        if (k % 2 == 0)
            return nCr(-n + k - 1, k);
        else
            return -nCr(-n + k - 1, k);
    }
    if (k > n)
        return 0;
    if (k > n / 2)
        k = n - k;
    if (nCr_arr == null) {
        synchronized (Util.class) {
            if (nCr_arr == null)
                nCr_arr = new long[n + 1][];
        }
    }
    if (nCr_arr.length <= n) {
        synchronized (Util.class) {
            if (nCr_arr.length <= n) {
                long[][] newNCR = new long[n + 1][];
                System.arraycopy(nCr_arr, 0, newNCR, 0, nCr_arr.length);
                nCr_arr = newNCR;
            }
        }
    }
    if (nCr_arr[n] == null) {
        synchronized (Util.class) {
            if (nCr_arr[n] == null)
                nCr_arr[n] = new long[k + 1];
        }
    }
    if (nCr_arr[n].length <= k) {
        synchronized (Util.class) {
            if (nCr_arr[n].length <= k) {
                long[] newNCR = new long[k + 1];
                System.arraycopy(nCr_arr[n], 0, newNCR, 0,
                        nCr_arr[n].length);
                nCr_arr[n] = newNCR;
            }
        }
    }
    if (nCr_arr[n][k] == 0) {
        if (k == 0)
            nCr_arr[n][k] = 1;
        else
            nCr_arr[n][k] = nCr(n, k - 1) * (n - (k - 1)) / k;
    }
    return nCr_arr[n][k];
}
}

Answer 1

私はそれを静的にしないようにすることになりました。スレッドがNCR値を取得する必要がある場合、新しい係数オブジェクトを作成し、それを保持します。

Answer 2

さて、コードを次のように変更して、いつでも再確認されたロックを避けることができます。

if (nCr_arr == null) {
    synchronized (Util.class) {
        if (nCr_arr == null)
            nCr_arr = new long[n + 1][];
    }
}

これに：

synchronized (Util.class) {
    if (nCr_arr == null)
        nCr_arr = new long[n + 1][];
}

パフォーマンスの影響は非常に少ないと思います。

Answer 3

これを最適化する必要がありますか？実行中のコードをプロファイルして、シングルロックが高すぎることを発見しましたか？

Answer 4

または、新しいJava Concurrency APIを使用してコードを書き換えます http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/readwritelock.htmlそして、本当に必要な場合にのみ書き込みロックを取得します。

Answer 5

コードの非常にパフォーマンスの重要な部分でこれを使用していることを考えると、係数へのアクセスごとにいくつかの追加比較を実行する必要があるため、怠zyな初期化のアイデアを捨てることをお勧めします。

代わりに、ライブラリのユーザーに、初期化時に必要な係数の数を手動で指定するように要求します。または、ユーザーが必要とする可能性が高い以上にプリピュートします - N <1000のすべてのNCKを1 MBのメモリに適合させることができます。

PS：再帰式を使用して係数を計算することをお勧めしますか？

c[n][k] = c[n-1][k-1] + c[n-1][k]

それはそれほど重要ではありませんが、必要なときに複雑な式に使用する理由 パスカルの三角形?

Answer 6

結果が計算されると、結果のキャッシュが構築されているように見えます。そのため、2つのINT値を1つのロングに組み合わせたキーを構築することで、同時マップを使用して結果を保持できます。

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public final class Util {
    /**
     * Static array of nCr values
     */
    private static final ConcurrentMap<Long,Long> CACHE = 
        new ConcurrentHashMap<Long, Long>();

    /**
     * Calculate binomial coefficient (n k)
     * 
     * @param n
     *            n
     * @param k
     *            k
     * @return n choose k
     */
    public static long nCr(int n, int k) {
        if (k < 0)
            throw new ArithmeticException("Cannot choose a negative number");
        if (n < 0) {
            if (k % 2 == 0)
                return nCr(-n + k - 1, k);
            else
                return -nCr(-n + k - 1, k);
        }

        if (k > n)
            return 0;
        if (k > n / 2)
            k = n - k;

        final long key = (n << 32L) + k;

        Long value = CACHE.get(key);
        if (value != null) {
            return value.longValue();
        } 

        long result;

        if (k == 0)
            result = 1;
        else
            result = nCr(n, k - 1) * (n - (k - 1)) / k;

        CACHE.put(key, result);

        return result;
    }
}

Answer 7

元のコードには、あまりにも多くのレース条件があります。手始めに、不揮発性のNCR_ARRを更新し、イディオムを再確認することを望んでいます。揮発性を宣言することは、キャッシュの目的を完全に打ち負かします。適切なコードは、CAS以外の同期をまったく使用しないでください。

CHMもここでも非常に悪い選択です（また、CHMはうまく尺度ではありません）。 （また、KeyがValueofの仕組みについて非常に良いb/cではない限り、Hotspotに適切にインラキングすることはできません。

誰かが（まだ）コードの実行方法に興味がある場合は、メモをドロップしてください。乾杯