Databases
StackOverflow2013
Postsdbo
PODouble-checked locking for growable array of binomial coefficients
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODouble-checked locking for growable array of binomial coefficients
    primarykey
    data
    text
    <p>I'm trying to use double-checked locking to maintain an array of binomial coefficients, but I read recently that double-checked locking doesn't work. Efficiency is extremely important so using volatile isn't an option unless it's only inside the conditional statements. I can't see a way to use a static class with a singleton object (this is part of a framework and I don't know what kinds of numbers people will need to use the function for so I can't guess what the maximum chosen value will be or whether the function will be used at all). The only thing I can think of is to make everything not static and insist that each thread that needs to use this method instantiate a Choose object with its own array. It seems like that shouldn't be necessary.</p> <pre><code>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 &lt; 0) throw new ArithmeticException("Cannot choose a negative number"); if (n &lt; 0) { if (k % 2 == 0) return nCr(-n + k - 1, k); else return -nCr(-n + k - 1, k); } if (k &gt; n) return 0; if (k &gt; 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 &lt;= n) { synchronized (Util.class) { if (nCr_arr.length &lt;= 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 &lt;= k) { synchronized (Util.class) { if (nCr_arr[n].length &lt;= 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]; } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USdspyz
    1. USdspyz
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COI would recommend making that a real class. What happens if someone calls your method a second time with a larger `n`? The array will have been initialized but will not be large enough. Not only that, if there are threads that use this static method concurrently you will have serous problems.
      singulars
      1. PODouble-checked locking for growable array of binomial coefficients
      1. USKevin Brock
    2. COAlso, if you do not expect concurrent use then eliminate that synchronized block since it no longer matters, and then document this thoroughly. You wouldn't need to worry about locking at all if you are just using this in a single thread. But, as my comment above, if you are using this with multiple threads you have a lot of other problems.
      singulars
      1. PODouble-checked locking for growable array of binomial coefficients
      1. USKevin Brock
    3. COSorry, missed that you are attempting to expand the array in a subsequent test. There still are concurrency problems here with the later assignments.
      singulars
      1. PODouble-checked locking for growable array of binomial coefficients
      1. USKevin Brock
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload