boolean [] vs. BitSet : 어느 것이 더 효율적입니까?

boolean [] vs. BitSet : 어느 것이 더 효율적입니까?

---

메모리 및 CPU 사용량 측면에서 더 효율적인 것은 무엇입니까 boolean? -배열 또는 BitSet? 특정 BitSet 메서드는 사용되지 않고 get / set / clear (배열에 대해 각각 ==, =, Arrays.fill) 만 사용됩니다.

---

Sieve가있는 Sun JDK 1.6 컴퓨팅 프라임을 사용한 일부 벤치 마크에서 (예열을위한 10 회 반복 중 최고, JIT 컴파일러에 기회 제공, 임의 스케줄링 지연 제외, Core 2 Duo T5600 1.83GHz) :

BitSet은 매우 작은 크기를 제외하고는 boolean []보다 메모리 효율성이 높습니다. 배열의 각 부울은 바이트를 사용합니다. runtime.freeMemory ()의 숫자는 BitSet에 대해 약간 혼란 스럽지만 적습니다.

boolean []은 매우 큰 크기를 제외하면 CPU 효율이 더 높습니다. 예를 들어, 크기가 1 백만인 경우 boolean []은 약 4 배 더 빠릅니다 (예 : 6ms 대 27ms), 천만 및 1 억의 경우 거의 균등합니다.

---

• Boolean[] 부울 값당 약 4-20 바이트를 사용합니다.
• boolean[] 부울 값당 약 1 바이트를 사용합니다.
• BitSet 부울 값당 약 1 비트를 사용합니다.

메모리 크기는 문제가되지 않을 수 있습니다.이 경우 boolean []이 코딩하기 더 간단 할 수 있습니다.

---

질문의 여지가 있지만 스토리지가 우려되는 경우 Huffman 압축 을 살펴볼 수 있습니다 . 예를 들어, 00000001는 주파수에 따라 {(7)0, (1)1}. 보다 "무작위 화 된"문자열 00111010은 예를 들어보다 복잡한 표현이 필요하며 더 {(2)0, (3)1, (1)0, (1)1, (1)0}많은 공간을 차지합니다. 비트 데이터의 구조에 따라 BitSet.

---

여기에서 부울 [] [] 삼각 행렬과 BitSet [] 삼각 행렬을 비교하는 메모리 / 시간 벤치 마크를 볼 수 있습니다.

(size * (size-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";
    }
}

---

As for memory, the documentation for a BitSet has pretty clear implications. In particular:

Every bit set has a current size, which is the number of bits of space currently in use by the bit set. Note that the size is related to the implementation of a bit set, so it may change with implementation. The length of a bit set relates to logical length of a bit set and is defined independently of implementation.

The source for Java library classes is openly available and one can easily check this for themselves. In particular:

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

As for speed; it depends on what one is doing. In general, don't think about speed ahead of time; use whichever tool makes the most sense semantically and leads to the clearest code. Optimize only after observing that performance requirements aren't met and identifying bottlenecks.

Coming to SO and asking if A is faster than B is silly for many reasons, including but certainly not limited to:

1. It depends on the application, which nobody responding generally has access to. Analyze and profile it in the context it is being used in. Be sure that it's a bottleneck that's actually worth optimizing.
2. Questions like this that ask about speed generally show that the OP thinks they care about efficiency but wasn't willing to profile and didn't define performance requirements. Under the surface, that's usually a red flag that the OP is headed down the wrong path.

I know this is an old question but it came up recently; and I believe this is worth adding.

---

It depends as always. Yes BitSet is more memory efficent, but as soon as you require multithreaded access boolean[] might be the better choice. For example for computing primes you only set the boolean to true and therefore you don't really need synchronization. Hans Boehm has written some paper about this and the same technique can be used for marking nodes in graph.

---

Going from Java to CPU is totally VM specific. For instance, it used to be that a boolean was actually implemented as a 32-bit value (quite probably is true to this day).

Unless you know it is going to matter you are better off writing the code to be clear, profile it, and then fix the parts that are slow or consuming a lot of memory.

You can do this as you go. For instance I once decided to not call .intern() on Strings because when I ran the code in the profiler it slowed it down too much (despite using less memory).

---

BitSet은 메모리 및 CPU 효율성이 더 높다고 생각합니다. 내부적으로 비트를 int, long 또는 기본 데이터 유형으로 압축 할 수있는 반면 boolean []은 각 데이터 비트에 대해 바이트를 필요로합니다. 또한 다른 메서드 (및 또는 등)를 사용하는 경우 배열의 모든 요소를 ​​반복 할 필요가 없기 때문에 BitSet이 더 효율적임을 알 수 있습니다. 대신 비트 수학이 사용됩니다.

참고 URL : https://stackoverflow.com/questions/605226/boolean-vs-bitset-which-is-more-efficient