双检查锁定的锁定，以生长的二项式系数阵列

Question

我正在尝试使用双重检查的锁定来维护一系列二项式系数，但是最近我读到，双检查锁定不起作用。效率极为重要，因此，除非仅在条件语句内部，否则使用挥发性不是一种选择。我看不到一种使用单身对象使用静态类的方法（这是框架的一部分，我不知道人们需要哪种数字来使用该功能选择的值将是或是否完全使用该函数）。我唯一能想到的是使所有内容都不静态，并坚持使用此方法的每个线程将选择对象用自己的数组实例化。似乎不需要。

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并发API重写代码 http://download.oracle.com/javase/1.5.0/docs/api/java/java/util/concurrent/concurrent/locks/readwritelock.html并仅在真正需要的情况下才获得写锁。

Answer 5

鉴于您在代码的非常关键的部分中使用了此功能，我建议您放弃懒惰的初始化想法，因为它需要为每个系数访问进行几次其他比较。

相反，我要求您的库用户手动指定她在初始化时需要多少个系数。另外，我预先计算的内容比用户可能需要的更多 - 您可以将N <1000的所有NCK适合1 MB的内存。

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

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

这没关系，但是为什么需要在需要时使用复杂的公式 帕斯卡尔三角?

Answer 6

我看起来好像您是一个构建结果的构建缓存，因此您可以使用并发地图通过构建将2个INT值结合到单个长度的键来保存结果。

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之外不应使用Sync。

CHM在这里也是一个非常糟糕的选择（CHM也不能很好地扩展）。 （也要长时间使用键的功能不是很好的b/c，因此不能由热点正确地插入它，因为它并不总是创建对象，并且最终值字段也无济于事）

如果有人（仍然）感兴趣的如何执行代码，请放下便条。干杯