Ricontrollato bloccaggio matrice growable di coefficienti binomiali

Question

Sto cercando di utilizzare ricontrollato bloccaggio per mantenere una matrice di coefficienti binomiali, ma ho letto recentemente che interblocco ricontrollato non funziona. L'efficienza è estremamente importante in modo da utilizzare volatile non è un'opzione meno che non sia solo all'interno delle istruzioni condizionali. Non riesco a vedere un modo per utilizzare una classe statica con un oggetto Singleton (questo è parte di un quadro e non so che tipo di numeri persone avranno bisogno di utilizzare la funzione per cui non posso immaginare quello che la massima valore scelto sarà o se la funzione verrà usato affatto). L'unica cosa che mi viene in mente è quello di rendere tutto ciò che non statica e insistere sul fatto che ogni thread che deve utilizzare questo metodo un'istanza di un oggetto scegliere con la propria matrice. Sembra che non dovrebbe essere necessario.

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

Ho finito appena rendendolo non statica. Se un bisogno di filo per ottenere valori di NCR si crea un nuovo oggetto coefficiente e tiene su di esso.

Answer 2

Bene, si può sempre evitare la doppia verificato il blocco modificando il codice:

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

a questo:

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

scommetto l'impatto sulle prestazioni sarebbe molto piccola.

Answer 3

Sei sicuro è necessario ottimizzare questo? Avete profilata l'esecuzione di codice e trovato il singolo blocco è troppo costoso?

Answer 4

O riscrivere il codice utilizzando le nuove API Java Concurrency http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html e di ottenere blocco in scrittura solo se veramente necessario.

Answer 5

Dato che si sta utilizzando questo in una performance parte molto critica del codice, vi consiglio di ammaraggio l'idea di inizializzazione pigra, perché richiede diverse comparazioni supplementari da erogare per ogni accesso ad un coefficiente.

Invece, mi piacerebbe costringe l'utente della vostra libreria per specificare manualmente il numero di coefficienti di cui ha bisogno in fase di inizializzazione. In alternativa, mi piacerebbe Precompute più che l'utente è ogni probabilità di necessità -. Si può andare bene tutto NCK per n <1000 in 1 MB di memoria

PS: potrei suggerire di usare la formula ricorsiva per calcolare un coefficiente

?

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

E non importa molto, ma perché l'uso di formula complicata quando è necessario Triangolo di Tartaglia ?

Answer 6

I si presenta come una costruzione di una cache dei risultati come essi vengono calcolati, così si potrebbe utilizzare una mappa concorrente a contenere i risultati con la costruzione di una chiave che unisce i 2 valori int in un unico lungo.

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

Il codice originale ha troppi condizioni di gara. Per cominciare non puoi aggiornare non volatile nCr_arr e di speranza per il doppio-check linguaggio al lavoro. Dichiarandolo volatili sconfigge completamente lo scopo della cache in qualche modo. il codice corretto non dovrebbe usare la sincronizzazione a tutti, ma CAS.

CHM è una pessima scelta anche qui (anche CHM non scala bene). (Anche utilizzando Lunga come chiave non è molto buona b / c di come funziona valueOf, non può essere adeguatamente inline da hotspot in quanto non sempre creare un oggetto ed il campo Valore finale non aiuta)

Se qualcuno è (ancora) interessate come fare il codice, rilasciare una nota. Acclamazioni