Revérifié verrouillage pour le tableau Growable des coefficients binomiaux

Question

Je suis en train d'utiliser revérifié de verrouillage pour maintenir un tableau de coefficients binomiaux, mais je lu récemment que le verrouillage revérifié ne fonctionne pas. L'efficacité est extrêmement important pour l'utilisation volatile n'est pas une option à moins que ce n'est que dans les instructions conditionnelles. Je ne vois pas un moyen d'utiliser une classe statique avec un objet singleton (cela fait partie d'un cadre et je ne sais pas ce genre de chiffres les gens devront utiliser la fonction pour donc je ne peux pas deviner ce que le maximum valeur choisie sera ou si la fonction sera utilisée du tout). La seule chose que je peux penser est tout à fait pas statique et insister pour que chaque thread a besoin d'utiliser cette méthode instancier un objet Choisissez avec son propre tableau. Il semble que ce ne devrait pas être nécessaire.

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

J'ai fini juste faire ce pas statique. Si un besoin de fil pour obtenir des valeurs nCr, il crée un nouvel objet de coefficient et tient sur elle.

Answer 2

Eh bien, vous pouvez toujours éviter une double vérification de verrouillage en modifiant le code de:

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

à ceci:

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

Je parie que l'impact de la performance serait très faible.

Answer 3

Êtes-vous sûr que vous devez optimiser cela? Avez-vous le code en cours d'exécution et PROFILES trouvé la serrure simple est trop cher?

Answer 4

Ou réécrire votre code en utilisant la nouvelle API Java Concurrency http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html et obtenir un verrou en écriture que si vraiment nécessaire.

Answer 5

Étant donné que vous utilisez ce dans une performance très partie essentielle de votre code, je vous recommande d'amerrissage l'idée d'initialisation paresseux, car il nécessite plusieurs comparaisons supplémentaires à effectuer pour chaque accès à un coefficient.

Au lieu de cela, je voudrais demander à l'utilisateur de votre bibliothèque pour spécifier manuellement le nombre de coefficients dont elle a besoin au moment de l'initialisation. Sinon, je Précalculer plus que l'utilisateur est tout probablement besoin -. Vous pouvez répondre à tous NCK pour n <1000 dans 1 Mo de mémoire

PS: Puis-je vous suggère d'utiliser la formule récursive pour calculer un coefficient

?

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

Il ne sera pas beaucoup d'importance, mais pourquoi utiliser la formule compliquée quand vous avez besoin Pascals Triangle ?

Answer 6

Je vous ressemble un bâtiment un cache des résultats car ils sont calculés, de sorte que vous pouvez utiliser une carte concurrente pour maintenir les résultats en construisant une clé qui combine les 2 valeurs int en une seule longue.

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

Le code d'origine a beaucoup trop de conditions de course. Pour commencer, vous ne pouvez pas mettre à jour nCr_arr non volatile et d'espoir pour idiome revérifier au travail. Déclarant volatile contrecarre totalement le but du cache en quelque sorte. code approprié ne doit pas utiliser la synchronisation du tout, mais CAS.

CHM est un très mauvais choix ici aussi (aussi bien CHM n'échelle). (Aussi longtemps que l'utilisation clé est pas très bon b / c de la façon dont fonctionne valueOf, il ne peut pas être correctement inline par hotspot, car il ne crée pas toujours un objet et champ de valeur finale ne soit pas d'aide)

Si quelqu'un est (encore) intéressé comment faire le code, déposer une note. Vive