A comprobar el bloqueo de matriz de coeficientes binomiales growable

Question

Estoy tratando de utilizar una doble comprobación de bloqueo para mantener un conjunto de coeficientes de dos términos, pero he leído recientemente que el bloqueo doble comprobación no funciona. La eficiencia es muy importante por lo que usar volátil no es una opción a menos que sea sólo dentro de las sentencias condicionales. No puedo ver una manera de utilizar una clase estática con un objeto Singleton (esto es parte de un marco y no sé lo que se necesita este tipo de números a la gente a utilizar la función para lo que no puedo adivinar lo que el máximo valor elegido será o si la función se utiliza en absoluto). Lo único que se me ocurre es hacer todo lo que no es estático e insistir en que cada subproceso que tiene que utilizar este método una instancia de un objeto con elegir su propia matriz. Parece que no debería ser necesario.

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

Acabé lo que no es estática. Si un hilo necesidades para obtener los valores de nCr, se crea un nuevo objeto coeficiente y se aferra a él.

Answer 2

Bueno, siempre podría evitar la doble comprobado bloqueo al cambiar el código de:

if (nCr_arr == null) {
    synchronized (Util.class) {
        if (nCr_arr == null)
            nCr_arr = new long[n + 1][];
    }
}

a esto:

synchronized (Util.class) {
    if (nCr_arr == null)
        nCr_arr = new long[n + 1][];
}

apuesto a que el impacto en el rendimiento sería muy pequeño.

Answer 3

¿Está seguro que necesita para optimizar esto? Tiene perfila la ejecución de código y encontrado el único bloqueo es demasiado caro?

Answer 4

O reescribir el código utilizando la nueva API de Java concurrencia http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html y obtener el bloqueo de escritura sólo si realmente se necesita.

Answer 5

Teniendo en cuenta que está usando esto en una actuación parte crítica muy de su código, recomiendo abandonando la idea perezosa inicialización, ya que requiere varias comparaciones adicionales que se deben realizar para cada acceso a un coeficiente.

En su lugar, me requiere que el usuario de la biblioteca para especificar manualmente el número de coeficientes que necesita en tiempo de inicialización. Por otra parte, me gustaría precomputamos más que el usuario es probable que cada necesidad -. Puede adaptarse a todos NCK para n <1000 en 1 MB de memoria

PS: ¿Puedo sugerir que utilice la fórmula recursiva para calcular un coeficiente

?

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

no importa mucho, pero ¿por qué el uso de fórmula complicada cuando se necesita Triángulo de Pascal

Answer 6

Me parece que la construcción de una memoria caché de los resultados a medida que se calculan, por lo que podría utilizar un mapa concurrente para contener los resultados mediante la construcción de una clave que combina los 2 valores enteros en una sola largas.

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

El código original tiene demasiadas condiciones de carrera. Para empezar no puedes actualizar nCr_arr no volátil y la esperanza de una doble comprobación lenguaje de trabajo. Declarándolo volátil derrota totalmente el propósito de la caché de alguna manera. código apropiado no debe utilizar la sincronización en absoluto, sino CAS.

CHM es una muy mala elección aquí también (también CHM no escala bien). (También usando larga como la clave no es muy buena b / c de cómo funciona valueOf, que no puede ser adecuadamente inlined por punto de acceso ya que no siempre se crea un objeto y campo de valor final no ayuda tampoco)

Si alguien es (todavía) interesados ??cómo hacer el código, la caída de una nota. Saludos