0

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

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];
}
}
4

7 に答える 7

0

計算時に結果のキャッシュを構築しているように見えます。したがって、並行マップを使用して、2つのint値を1つのlongに結合するキーを構築することで結果を保持できます。

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;
    }
}
于 2010-08-30T17:36:29.870 に答える
0

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

代わりに、ライブラリのユーザーに、初期化時に必要な係数の数を手動で指定するように要求します。または、ユーザーが必要とする可能性がある以上の値を事前に計算します。n<1000のすべてのnCkを1MBのメモリに収めることができます。

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

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

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

于 2010-08-30T17:30:51.503 に答える
0

元のコードには競合状態が多すぎます。手始めに、不揮発性の nCr_arr を更新できず、ダブルチェック イディオムが機能することを期待します。volatile と宣言すると、キャッシュの目的が完全に無効になります。適切なコードでは、同期をまったく使用しないでください。ただし、CAS は使用しないでください。

ここでも CHM は非常に悪い選択です (また、CHM はうまく拡張できません)。(また、Long を key として使用することは、valueOf がどのように機能するかという点であまり良くありません。常にオブジェクトを作成するとは限らず、最終的な値フィールドも役に立たないため、ホットスポットによって適切にインライン化することはできません)

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

于 2011-01-04T01:56:14.303 に答える
0

コードを次のように変更することで、ダブル チェック ロックを常に回避できます。

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][];
}

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

于 2010-08-29T20:12:24.353 に答える
0

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

于 2010-08-30T16:52:41.687 に答える
0

これを最適化する必要がありますか? 実行中のコードをプロファイリングして、単一のロックが高すぎることに気付きましたか?

于 2010-08-30T09:21:31.147 に答える
0

結局、静的ではないようにしました。スレッドが nCr 値を取得する必要がある場合、スレッドは新しい Coefficient オブジェクトを作成し、それを保持します。

于 2010-09-11T19:16:04.817 に答える