10億のデータから数字を素早く見つける方法 | 定番アルゴリズムBitMapの詳しい説明

序文

多くの人は、BitMap は文字通りビットマップを意味すると考えています。実際、より正確には、ビットベースのマッピングと翻訳されます。どのように理解しますか?

問題の紹介

順序付けされていない境界付き int 配列 {1,2,5,7} があり、これは 44=16 バイトのメモリを占有すると推定されています。数字は 4 つしかないため、必要な数字をすばやく見つけるのは簡単です。しかし、そのような数字が 10 億個あり、重複もソートもされていない unsigned int 整数が 10 億個ある場合、整数が与えられたら、どうしますか?

要件分析: Java の Int 型のストレージは 4 バイト、32 ビットを占有します。 10億4/(102410241024)=約3.72G。これだけ大量のデータを検索・ソートすると、メモリが破綻してしまうでしょう。このデータは一度に読み込む必要はなく、保存する必要があり、保存すると必然的にIOを消費してしまうという意見もあります。当社は高パフォーマンスを重視しているため、このソリューションはまったく考慮されていません。

[[330308]]

問題分析

BitMap の考え方を使って解決すれば、はるかに良い結果が得られます。では、BitMap はどのように解決するのでしょうか? 次のようにします。

1 バイトは 8 ビットを占めます。各ビットの値が存在するか存在しないか、つまり 2 進数で 0 または 1 の場合、ビットの位置が配列値の有無を表す場合、0 は値が現れていないことを意味し、1 は配列値が出現したことを意味します。データも記述できないのでしょうか？詳細は以下の通りです。

すごいと思いませんか? 10億のデータに必要なスペースが3.72G/32だとすると、32ビットを占めるデータは1ビットしか占めなくなり、ソートはもちろんのこと、多くのスペースを節約できます。すべてがとてもスムーズに思えます。このようなデータには相関関係はありません。読み取りたい場合は、マルチスレッドを使用して読み取ることができます。時間の計算量も O(Max/n) です。ここで、Max は byte[] 配列のサイズ、n はスレッドサイズです。

3. アプリケーションとコード

BitMap がこれだけの機能しか持っていないと、エレガントさが足りない気がします。これからもその魅力を味わい続けていきましょう。次の計算アイデアは、実際にはビットの論理演算によって得られます。この種の論理演算に類似したアプリケーションシナリオは、権限計算で使用できます。

コードを見る前に、まず 1 つの問題を明確にしましょう。それは、数値のインデックス番号をすばやく見つける方法、つまり、byte[index] のインデックスが何であり、それがどの位置であるかを調べる方法です。例えば、add(14)。 14はbyte[0]のマッピング範囲外であり、byte[1]の範囲内にあります。では、そのインデックスを素早く見つけるにはどうすればよいでしょうか?インデックス番号を見つけたら、どうやって見つけるのでしょうか? Index(N)はNのインデックス番号を表し、Position(N)はNの位置番号を表します。

インデックス(N) = N/8 = N >> 3;
位置(N) = N%8 = N & 0x07;

(1) 加算(int 数値)

ビットマップにデータを追加したい場合はどうすればいいでしょうか? 心配しないでください。非常にシンプルで魔法のような方法です。上記で分析したように、add の目的は位置を 0 から 1 に変更することです。他の位置は変更されません。

コード例:

パブリックvoid追加( int数値) {
        // num/8はbyte[]のインデックスを取得します 
 int配列インデックス = num >> 3; 
         
        // num%8 はバイト[インデックス]内の位置を取得します
int位置 = num & 0x07; 
         
        // 位置だけ左に 1 シフトすると、その位置は当然 1 になり、その後、前のデータに対して | を実行して、位置が 1 に置き換えられます。
        ビット[配列インデックス] |= 1 << 位置;
    }

(2) クリア(int num)

1 を左にシフトし、それを否定し、最後に byte[index] と AND します。

コード例:

パブリックvoidクリア( int num) {
        // num/8はbyte[]のインデックスを取得します 
 int配列インデックス = num >> 3; 
         
        // num%8 はバイト[インデックス]内の位置を取得します
int位置 = num & 0x07; 
         
        // 位置だけ左に 1 移動した後、その位置は当然 1 になります。次にそれを否定し、現在の値と & して現在の位置をクリアします。
        bits[配列インデックス] &= ~(1 << 位置); 
 
    }

(3) 含む(int 数値)

コード例:

パブリックブール値contain( int num){
       // num/8はbyte[]のインデックスを取得します 
 int配列インデックス = num >> 3; 
        
       // num%8 はバイト[インデックス]内の位置を取得します
int位置 = num & 0x07; 
        
       //位置だけ左に 1 シフトすると、その位置は当然 1 になります。次に、前のデータと & を実行して、0 かどうかを判断します。
戻り値(bits[arrayIndex] & (1 << position)) != 0;
   }

完全なコードは次のとおりです。

パブリッククラスBitMap {
    //データを保存する
    プライベートバイト[]ビット; 
     
    //保存できるデータ量
    プライベートint容量; 
     
     
パブリックビットマップ( int容量){
        this.capacity = 容量; 
         
        //1 ビットで 8 つのデータを格納できるので、容量データには何ビット必要でしょうか? 容量/8+1、3 ビット右にシフトすると 8 で割るのと同じになります
        ビット = 新しいバイト[(容量>>3)+1];
    } 
     
パブリックvoid追加( int数値) {
        // num/8はbyte[]のインデックスを取得します 
 int配列インデックス = num >> 3; 
         
        // num%8 はバイト[インデックス]内の位置を取得します
int位置 = num & 0x07; 
         
        // 位置だけ左に 1 シフトすると、その位置は当然 1 になり、その後、前のデータに対して | を実行して、位置が 1 に置き換えられます。
        ビット[配列インデックス] |= 1 << 位置;
    } 
     
パブリックブール値contain( int num){
        // num/8はbyte[]のインデックスを取得します 
 int配列インデックス = num >> 3; 
         
        // num%8 はバイト[インデックス]内の位置を取得します
int位置 = num & 0x07; 
         
        //位置だけ左に 1 シフトすると、その位置は当然 1 になります。次に、前のデータと & を実行して、0 かどうかを判断します。
戻り値(bits[arrayIndex] & (1 << position)) != 0;
    } 
     
パブリックvoidクリア( int num) {
        // num/8はbyte[]のインデックスを取得します 
 int配列インデックス = num >> 3; 
         
        // num%8 はバイト[インデックス]内の位置を取得します
int位置 = num & 0x07; 
         
        // 位置だけ左に 1 移動した後、その位置は当然 1 になります。次にそれを否定し、現在の値と & して現在の位置をクリアします。
        bits[配列インデックス] &= ~(1 << 位置); 
 
    } 
     
公共 静的void main(String[] args) {
        ビットマップ ビットマップ = 新しいビットマップ(100);
        ビットマップを追加します（7）;
        System.out.println ( "7 を正常に挿入しました" ); 
         
        ブール isexsit = bitmap.contain(7);
        システム.out.println ( "7が存在します:" +isexsit); 
         
        ビットマップをクリア(7);
        isexsit = ビットマップ.contain(7);
        システム.out.println ( "7が存在します:" +isexsit);
    }
 }