منطقية[] مقابلBitSet:والتي هي أكثر كفاءة ؟

Question

ما هي أكثر كفاءة من حيث الذاكرة و CPU — مجموعة من booleans أو BitSet?محددة BitSet الطرق لا تستخدم فقط الحصول على/مجموعة/واضح (==, =, صفائف.ملء على التوالي في مجموعة).

Answer 1

ومن بعض المعايير مع صن JDK 1.6 يعبي الحوسبة مع غربال (أفضل من 10 التكرار في عملية الاحماء، وإعطاء مترجم JIT فرصة، واستبعاد تأخير مواعيد عشوائية، كور 2 ديو T5600 1.83GHz):

وBitSet هو أكثر كفاءة من ذاكرة منطقية [] إلا لأحجام صغيرة جدا. كل منطقية في مجموعة يأخذ بايت. الأرقام من runtime.freeMemory () هي مشوشة قليلا عن BitSet، ولكن أقل من ذلك.

ومنطقية [] هو أكثر كفاءة وحدة المعالجة المركزية إلا لأحجام كبيرة جدا، حيث أنهم على وشك ذلك. على سبيل المثال، لحجم 1000000 منطقية [] حوالي أربع مرات أسرع (على سبيل المثال 6ms مقابل 27ms)، لمدة عشرة ومئات من ملايين أنهم على وشك ذلك.

Answer 2

• Boolean[] يستخدم حوالي 4-20 بايت لكل قيمة منطقية.
• boolean[] يستخدم حوالي 1 بايت لكل قيمة منطقية.
• BitSet يستخدم حوالي 1 بت لكل قيمة منطقية.

حجم الذاكرة قد لا يكون مشكلة بالنسبة لك في هذه الحالة المنطقية[] قد يكون أبسط إلى رمز.

Answer 3

وواليسار حقل بت لسؤالك، ولكن إذا التخزين هو مصدر قلق قد ترغب في النظر في هوفمان ضغط . على سبيل المثال، يمكن أن تقلص 00000001 بنسبة تردد إلى شيء يعادل {(7)0, (1)1}. ومن شأن المزيد من "عشوائية" 00111010 سلسلة تتطلب تمثيل أكثر تعقيدا، على سبيل المثال {(2)0, (3)1, (1)0, (1)1, (1)0}، وتأخذ مساحة أكبر. اعتمادا على بنية البيانات الخاصة بك قليلا، قد تحصل على بعض الفوائد التخزين من استخدامه، وراء BitSet.

Answer 4

أما عن الذاكرة ، وثائق BitSet جميلة آثار واضحة.على وجه الخصوص:

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

المصدر جافا مكتبة دروس متاحة و يمكن للمرء بسهولة هذا الاختيار لأنفسهم.على وجه الخصوص:

The internal field corresponding to the serialField "bits".
89 
90     private long[] words;

أما بالنسبة السرعة ؛ ذلك يعتمد على ما يقوم به.بشكل عام, لا تفكر بسرعة قبل الوقت ؛ استخدام أيهما أداة يجعل معظم معانيها لغويا يؤدي إلى أوضح رمز.تحسين فقط بعد أن لاحظت أن أداء متطلبات لم تتحقق وتحديد الاختناقات.

القادمة حتى يسأل إذا كان هو أسرع من ب سخيف لأسباب عديدة ، بما في ذلك ولكن بالتأكيد ليس على سبيل الحصر:

1. ذلك يعتمد على التطبيق الذي لا أحد يستجيب بشكل عام لديه حق الوصول إلى.تحليل الشخصية في سياق يتم استخدامه في.تأكد من أنه من عنق الزجاجة التي هي في الواقع يستحق الأمثل.
2. أسئلة من هذا القبيل أن يسأل عن السرعة عموما تبين أن المرجع يعتقد أنهم يهتمون الكفاءة ولكن لم يكن على استعداد الشخصي و لم تحدد متطلبات الأداء.تحت السطح ، التي عادة ما تكون حمراء العلم أن المرجع هو متوجه إلى الطريق الخطأ.

أعرف أن هذا هو السؤال القديم لكنه جاء في الآونة الأخيرة ؛ و أعتقد أن هذا يستحق إضافة.

Answer 5

وهذا يعتمد كما هو الحال دائما. نعم BitSet هو أكثر يتسم بفعالية الذاكرة، ولكن بمجرد تتطلب منطقية وصول مؤشرات [] قد يكون الخيار الأفضل. على سبيل المثال لحساب يعبي لك فقط تعيين منطقية إلى true، وبالتالي لا تحتاج تزامن حقا. هانز بوهم وقد كتب بعض ورقة حول هذا و نفس الأسلوب يمكن أن تستخدم لوضع العلامات على العقد في الرسم البياني.

Answer 6

وهنا يمكنك ان ترى الذاكرة / الوقت القياسي يقارن منطقي [] [] trianguar مصفوفة مقابل BitSet [] مصفوفة ثلاثية.

وأنا خلق، تعيين وقراءة (* حجم (حجم-1) / 2) القيم ومقارنة استخدام الذاكرة والوقت ...

وهذا الأمل مساعدة ...

وهنا هو رمز ... (مجرد رمز اختبار القذرة قوانينه، آسف.)

import java.util.BitSet;
import java.util.Date;

public class BooleanBitSetProfiler {

    Runtime runtime;
    int sum = 0;
    public void doIt() {

        runtime = Runtime.getRuntime();
        long[][] bitsetMatrix = new long[30][2];
        long[][] booleanMatrix = new long[30][2];
        int size = 1000;
        for (int i = 0; i < booleanMatrix.length; i++) {
            booleanMatrix[i] = testBooleanMatrix(size);
            bitsetMatrix[i] = testBitSet(size);
            size += 2000;
        }
        int debug = 1;
        for (int j = 0; j < booleanMatrix.length; j++){
            System.out.print(booleanMatrix[j][0] + ";");
        }
        System.out.println();
        for (int j = 0; j < booleanMatrix.length; j++){
            System.out.print(booleanMatrix[j][1] + ";");
        }
        System.out.println();
        for (int j = 0; j < bitsetMatrix.length; j++){
            System.out.print(bitsetMatrix[j][0] + ";");
        }
        System.out.println();
        for (int j = 0; j < bitsetMatrix.length; j++){
            System.out.print(bitsetMatrix[j][1] + ";");
        }
        System.out.println();
    }

    private long memory () {
        return runtime.totalMemory() - runtime.freeMemory();
    }
    private long[] testBooleanMatrix(int size) {
        runtime.gc();
        long startTime = new Date().getTime();
        long startMemory = memory();
        boolean[][] matrix = new boolean[size][];
        for (int i = 0; i < size; i++) {
            matrix[i] = new boolean[size - i - 1];
        }
        long creationMemory = memory();
        long creationTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = i % 2 == 0;
            }
        }
        long setMemory = memory();
        long setTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j]) sum++;
            }
        }
        long readTime = new Date().getTime();
        System.out.println("Boolean[][] (size " + size + ")");
        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));
        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");
        runtime.gc();
        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};
    }
    private long[] testBitSet(int size) {
        runtime.gc();
        long startTime = new Date().getTime();
        long startMemory = memory();
        BitSet[] matrix = new BitSet[size];
        for (int i = 0; i < size; i++) {
            matrix[i] = new BitSet(size - i - 1);
        }
        long creationMemory = memory();
        long creationTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].size(); j++) {
                matrix[i].set(j, (i % 2 == 0));
            }
        }
        long setMemory = memory();
        long setTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i].get(j)) sum++;
            }
        }
        long readTime = new Date().getTime();
        System.out.println("BitSet[] (size " + size + ")");
        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));
        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");
        runtime.gc();
        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};
    }

    private String printMem(long mem) {
        mem = mem / (1024*1024);
        return mem + "MB";
    }
    private String printTime(long milis) {
        int seconds = (int) (milis / 1000);
        milis = milis % 1000;
        return seconds > 0 ? seconds + "s " + milis + "ms" : milis + "ms";
    }
}

Answer 7

والانتقال من جافا إلى وحدة المعالجة المركزية هو تماما VM محددة. على سبيل المثال، كان عليه أن يكون هذا منطقي ونفذ فعلا كقيمة 32 بت (ربما تماما هو الصحيح حتى يومنا هذا).

وإذا لم تكن تعرف أنه ذاهب ليهم كنت أفضل حالا كتابة رمز لتكون واضحة، الشخصية، ومن ثم إصلاح الأجزاء التي تكون بطيئة أو تستهلك الكثير من الذاكرة.

ويمكنك القيام بذلك كما تذهب. على سبيل المثال قررت مرة واحدة ليست دعوة .intern () على سلاسل لأنه عندما ركضت التعليمات البرمجية في التعريف أنه تباطأ عليه كثيرا (على الرغم من استخدام ذاكرة أقل).

Answer 8

وأعتقد أن BitSet أكثر في الذاكرة وكفاءة حدة المعالجة المركزية، هو أن حزمة داخليا البتات إلى كثافة العمليات، يتوق، أو أنواع البيانات الأم، في حين أن منطقية [] يتطلب بايت لكل بت من البيانات. بالإضافة إلى ذلك، إذا كنت لاستخدام أساليب أخرى (و، أو، الخ)، وسوف تجد أن BitSet هو أكثر كفاءة، كما أن هناك حاجة لتكرار خلال كل عنصر من عناصر مجموعة. ويستخدم أحادي المعامل الرياضيات بدلا من ذلك.