java - 可增长的二项式系数数组的双重检查锁定

Question

我正在尝试使用双重检查锁定来维护一个二项式系数数组，但我最近读到双重检查锁定不起作用。效率非常重要，因此除非仅在条件语句中，否则不能选择使用 volatile。我看不到将静态类与单例对象一起使用的方法（这是框架的一部分，我不知道人们需要使用该函数来处理什么样的数字，所以我无法猜测最大值是多少选择的值将是或是否将使用该函数）。我唯一能想到的就是让一切都不是静态的，并坚持需要使用此方法的每个线程都用自己的数组实例化一个选择对象。看来这应该是不必要的。

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

score 0 · Accepted Answer

好吧，您总是可以通过更改以下代码来避免双重检查锁定：

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

我敢打赌，性能影响会非常小。

score 0 · Accepted Answer

0

您确定需要对此进行优化吗？你有没有分析过运行代码，发现单锁太贵了？

于 2010-08-30T09:21:31.147 回答

score 0 · Accepted Answer

或者使用新的 Java 并发 API http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html重写您的代码，并仅在确实需要时获取写锁。

score 0 · Accepted Answer

鉴于您在代码的性能非常关键的部分使用它，我建议放弃惰性初始化的想法，因为它需要为每次访问系数执行几次额外的比较。

相反，我会要求您的库的用户手动指定她在初始化时需要多少个系数。或者，我会预先计算超出用户可能需要的数量 - 您可以将 n < 1000 的所有 nCk 放入 1 MB 内存中。

PS：我可以建议您使用递归公式来计算系数吗？

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

没关系，但是当您需要帕斯卡三角形时，为什么要使用复杂的公式呢？

score 0 · Accepted Answer

我看起来像您在计算结果时构建缓存，因此您可以使用并发映射通过构建将 2 个 int 值组合成单个 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;
    }
}

score 0 · Accepted Answer

我最终只是让它不是静态的。如果线程需要获取 nCr 值，它会创建一个新的 Coefficient 对象并保留它。

score 0 · Accepted Answer

原始代码有太多的竞争条件。对于初学者，您无法更新非易失性 nCr_arr 并希望仔细检查习语能够正常工作。以某种方式将其声明为 volatile 完全违背了缓存的目的。正确的代码根本不应该使用同步，而是 CAS。

CHM 在这里也是一个非常糟糕的选择（CHM 也不能很好地扩展）。（同样使用 Long as key 对 valueOf 的工作方式不是很好的 b/c，它不能被热点正确内联，因为它并不总是创建一个对象并且最终值字段也无济于事）

如果有人（仍然）对如何编写代码感兴趣，请记下。干杯

java - 可增长的二项式系数数组的双重检查锁定

7 回答 7

Related

Reference