为什么要用BitSet - JAVA

BitSet适用于一类型boolean判断， Java的BitSet在这类型判断中非常高效。

举例说明：在判断前2000万数字中素数个数的程序中，如果使用最基本的素数判断代码：

package com;  
  
public class Sus {  
  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        int n = 20000000;  
        long start = System.currentTimeMillis();  
        int count = 0;  
        boolean is = false;  
        for(int i = 2;i <= n;i++){  
            for(int j = 2; j <= Math.sqrt(i);j++){  
                if( i % j == 0){  
                    is = true;  
                    break;  
                }  
            }  
            if(!is){  
                count++;  
            }  
            is = false;  
        }  
        long end = System.currentTimeMillis();  
        System.out.println("count = "+count);  
        System.out.println((end-start)+" milliseconds");  
  
    }  
  
}

则执行时间为：

count = 1270607

35153 milliseconds

而如果使用BitSet 位图提供的基于“开关”思想的素数判断代码：







package com;  
  
import java.util.BitSet;  
  
public class Sieve {  
      
    public static void main(String[] args){  
        int n = 20000000;  
        long start = System.currentTimeMillis();  
        BitSet b = new BitSet(n+1);  
        int count = 0;  
        int i;  
        for(i = 2; i <= n;i++){  
            b.set(i);  
        }  
        i = 2;  
        while(i*i <=n){  
            if(b.get(i)){  
                count++;  
                int k = 2 * i;  
                while(k <= n){  
                    b.clear(k);  
                    k +=i;  
                }  
            }  
            i++;  
        }  
        while(i <= n){  
            if(b.get(i)){  
                count++;  
            }  
            i++;  
        }  
        long end = System.currentTimeMillis();  
        System.out.println("count = " + count);  
        System.out.println((end-start) +" milliseconds");  
    }  
}

则执行时间为：

count = 1270607

248 milliseconds

我们可以看到，同样规模的数据，两者的执行效率差百倍之多，因此在某类可以用开关位判断的程序中，应该尽量使用BitSet。