代码之家 › 专栏 › 技术社区 › dspyz

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

binomial-coefficients double-checked-locking java-memory-model locking java

dspyz · 技术社区 · 15 年前

我试图使用双重检查锁定来维护二项式系数的数组,但是最近我读到双重检查锁定不起作用。效率是非常重要的,所以使用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];
}
}

7 回复 | 直到 15 年前

krtek 15 年前

好吧,您可以通过更改以下代码来避免双重检查锁定:

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

我打赌对性能的影响会很小。

user434722 15 年前

你确定要优化这个吗?你有没有分析过运行中的代码,发现单个锁太贵了?

krtek 15 年前

http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html 只有在真正需要的时候才能获得写锁。

meriton 15 年前

考虑到您在代码中对性能非常关键的部分使用了这个方法,我建议您放弃延迟初始化的想法,因为它需要为每次访问一个系数执行几个额外的比较。

相反,我要求库的用户手动指定初始化时需要多少个系数。或者,我会预计算比用户可能需要的更多的数据—您可以将n<1000的所有nCk放入1 MB内存中。

附言:我可以建议你用递归公式来计算系数吗?

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

这没什么关系,但你需要的时候为什么要用复杂的公式呢 Pascals Triangle ?

Michael Barker 15 年前

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

dspyz 15 年前

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

bestsss 15 年前

原来的代码有太多的竞争条件。对于初学者来说,您不能更新非易失性nCr\u arr,希望双重检查习惯用法能够工作。声明为volatile完全违背了缓存的目的。正确的代码不应该使用sync,而应该使用CAS。

CHM在这里也是一个非常糟糕的选择(CHM的伸缩性也不好)。(同样,只要key不是valueOf工作原理的很好的b/c,它就不能被hotspot正确内联,因为它并不总是创建对象,final value字段也没有帮助)

干杯