Двойная проверка блокировки для растущего массива биномиальных коэффициентов

Question

Я пытаюсь использовать двойную проверку блокировки, чтобы поддерживать массив биномиальных коэффициентов, но недавно я прочитал, что двойная проверка блокировки не работает.Эффективность чрезвычайно важна, поэтому использование 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];
}
}

Answer 1

В итоге я просто сделал это не статичным.Если поток должен получить значения nCr, он создает новый объект Coefficient и удерживает его.

Answer 2

В исходном коде слишком много условий гонки. Во-первых, вы не можете обновить энергонезависимую версию nCr_arr и надеяться, что идиома будет дважды проверена. Объявление его как volatile полностью нарушает назначение кеша. Правильный код не должен использовать синхронизацию вообще, кроме CAS.

CHM здесь тоже очень плохой выбор (также CHM плохо масштабируется). (Также использование ключа Long как ключа не очень хорошо из-за того, как работает valueOf, он не может быть должным образом встроен в точку доступа, поскольку он не всегда создает объект, и поле окончательного значения тоже не помогает)

Если кому-то (все еще) интересно, как сделать код, оставьте записку. Приветствия

Answer 3

Похоже, вы создаете кеш результатов по мере их вычисления, поэтому вы можете использовать параллельную карту для хранения результатов, создав ключ, который объединяет 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;
    }
}

Answer 4

Учитывая, что вы используете это в критически важной части вашего кода, я рекомендую отказаться от ленивой идеи инициализации, поскольку для каждого доступа к коэффициенту требуется выполнить несколько дополнительных сравнений.

Вместо этогоЯ бы потребовал, чтобы пользователь вашей библиотеки вручную указал, сколько коэффициентов ей нужно во время инициализации.В качестве альтернативы я бы рассчитал больше, чем может потребоваться пользователю - вы можете разместить все nCk для n <1000 в 1 МБ памяти. </p>

PS: Могу предложить вам использовать рекурсивную формулу для вычислениякоэффициент?

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

Это не будет иметь большого значения, но зачем использовать сложную формулу, когда вам нужно Треугольник Паскаля ?

Answer 5

Или переписать свой код с помощью нового Java Concurrency API http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html и получить блокировку записи только в случае необходимости.

Answer 6

Вы уверены, что вам нужно оптимизировать это? Вы профилировали работающий код и обнаружили, что одиночная блокировка слишком дорога?

Answer 7

Ну, вы всегда можете избежать двойной проверки блокировки, изменив код с:

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

Могу поспорить, что влияние на производительность будет очень небольшим.1007 *