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

Question

Я пытаюсь использовать блокировку с двойным проверкой для поддержки массива биномиальных коэффициентов, но недавно я прочитал, что блокировка с двойной проверкой не работает. Эффективность чрезвычайно важна, поэтому использование volatile не является вариантом, если только внутри условных операторов. Я не вижу способа использовать статический класс с одноэлементным объектом (это часть структуры, и я не знаю, какие числа людей должны будут использовать эту функцию, поэтому я не могу догадаться, что такое максимум выбранное значение будет или будет ли функция вообще использоваться). Единственное, о чем я могу думать, это сделать все, что не статично, и настаивать на том, чтобы каждый поток, который должен использовать этот метод, создавал экземпляр объекта Select со своим собственным массивом. Похоже, это не обязательно.

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

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

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

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

Answer 5

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

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

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

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

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

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.

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

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