Двойная проверка блокировки для растущего массива биномиальных коэффициентов
https://stackoverflow.com/questions/3596174
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь использовать блокировку с двойной проверкой для хранения массива биномиальных коэффициентов, но недавно прочитал, что блокировка с двойной проверкой не работает.Эффективность чрезвычайно важна, поэтому использование Летучих недопустимо, если только оно не используется только внутри условных операторов.Я не вижу способа использовать статический класс с одноэлементным объектом (это часть структуры, и я не знаю, для каких чисел людям понадобится использовать эту функцию, поэтому я не могу угадать, каков максимальный выбранное значение будет или будет ли функция использоваться вообще).Единственное, о чем я могу думать, это сделать все не статичным и настаивать на том, чтобы каждый поток, которому необходимо использовать этот метод, создавал экземпляр объекта 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];
}
}
Решение 6
Я закончил просто сделать его не статичным. Если нить должна получить значения NCR, он создает новый объект коэффициента и удерживает его.
Другие советы
Ну, вы всегда можете избежать двойной проверки блокировки, изменив код из:
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][];
}
Могу поспорить, что воздействие производительности было бы очень маленьким.
Вы уверены, что вам нужно оптимизировать это? Вы профилированные код и нашли один замок слишком дороги?
Или переписать свой код с помощью нового API Java Consurrence http://download.orcle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/readwritelock.html.И получить замок записи только в случае действительно необходимости.
Учитывая, что вы используете это в очень критической критической части вашего кода, я рекомендую раскрутить идею инициализации ленивой инициализации, поскольку для каждого доступа к коэффициенту необходимо выполнить несколько дополнительных сравнений для каждого доступа к коэффициенту.
Вместо этого мне требуется, чтобы пользователь вашей библиотеки вручную указать, сколько коэффициентов, которые ей нуждается в времени инициализации. В качестве альтернативы, я бы предварительно предвкушал больше, чем каждый пользователь, вероятно, понадобится - вы можете поместить все NCK для N <1000 на 1 МБ памяти.
PS: Могу ли я предложить вам использовать рекурсивную формулу для вычисления коэффициента?
c[n][k] = c[n-1][k-1] + c[n-1][k]
Это не имеет значения многое, но зачем использовать для сложной формулы, когда вам нужно Паскальс треугольник?
Я похоже, что вы строите кэш результатов, поскольку они рассчитаны, поэтому вы можете использовать одновременную карту для проведения результатов, создавая ключ, который сочетает в себе значения 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;
}
}
В исходном коде слишком много состояний гонки.Для начала вы не можете обновить энергонезависимый nCr_arr и надеяться, что идиома двойной проверки сработает.Объявление его изменчивым каким-то образом полностью противоречит цели кеша.Правильный код вообще не должен использовать синхронизацию, кроме CAS.
CHM здесь тоже очень плохой выбор (также CHM плохо масштабируется).(Кроме того, использование Long в качестве ключа не очень хорошо из-за того, как работает valueOf, его нельзя правильно встроить в горячую точку, поскольку он не всегда создает объект, и поле конечного значения тоже не помогает)
Если кому-то (все еще) интересно, как написать код, напишите.Ваше здоровье
