قفل مزدوج لصالح مجموعة من معاملات الحدين

Question

أحاول استخدام القفل المزدوج للحفاظ على مجموعة من معاملات الحدين ، لكنني قرأت مؤخرًا أن القفل الذي تم فحصه مزدوجًا لا يعمل. الكفاءة مهمة للغاية ، لذا فإن استخدام التقلب ليس خيارًا ما لم يكن داخل البيانات الشرطية فقط. لا أستطيع رؤية طريقة لاستخدام فئة ثابتة مع كائن مفردة (هذا جزء من إطار عمل ولا أعرف أنواع الأرقام التي سيحتاجها الناس إلى استخدام الوظيفة لذلك لا يمكنني تخمين ما هو الحد الأقصى ستكون القيمة المختارة أو ما إذا كانت الوظيفة ستستخدم على الإطلاق). الشيء الوحيد الذي يمكنني التفكير فيه هو جعل كل شيء غير ثابت ويصر على أن كل مؤشر ترابط يحتاج إلى استخدام هذه الطريقة على إنشاء كائن اختيار مع صفيفه الخاص. يبدو أن هذا لا ينبغي أن يكون ضروريًا.

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 ، فإنه ينشئ كائنًا جديدًا معاملًا ويتمسك به.

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 New Java Concurrency http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/readwritelock.htmlوالحصول على قفل الكتابة فقط إذا لزم الأمر حقًا.

Answer 5

بالنظر إلى أنك تستخدم هذا في جزء مهم للغاية من الكود الخاص بك ، أوصي بالتخلي عن فكرة التهيئة البطيئة ، لأنها تتطلب إجراء عدة مقارنات إضافية لكل وصول إلى معامل.

بدلاً من ذلك ، سأطلب من مستخدم مكتبتك تحديد عدد المعاملات التي تحتاجها يدويًا في وقت التهيئة. بدلاً من ذلك ، سأحتاج إلى حاجة إلى أكثر من المستخدم أكثر من احتمال حاجة - يمكنك وضع جميع NCK لـ N <1000 إلى 1 ميغابايت من الذاكرة.

ملاحظة: هل أقترح عليك استخدام الصيغة العودية لحساب المعامل؟

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

لن يكون الأمر مهمًا ، ولكن لماذا استخدم الصيغة المعقدة عند الحاجة مثلث Pascals?

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 جيدًا). (أيضًا باستخدام المفتاح ليس جيدًا جدًا B/C لكيفية عمل ValueOF ، لا يمكن إدانته بشكل صحيح بواسطة نقطة ساخنة لأنه لا ينشئ دائمًا كائنًا ولا يساعد حقل القيمة النهائية أيضًا)

إذا كان أي شخص مهتمًا (لا يزال) كيفية القيام بالرمز ، فقم بإسقاط ملاحظة. هتافات