BitmapのJavaでの応用
2558 ワード
一、40億のデータ並べ替え問題
最大40億個のランダムに配列された32ビットの整数を含むシーケンスファイルを指定し、ファイルにない32ビットの整数を見つけます(ファイルには少なくともこのような数が欠けています.なぜですか).十分なメモリがある場合、この問題を解決するにはどうすればいいですか?(プログラミング珠玉)
二、BitMapを応用してビッグデータを保存する
データの存在性はbitビット上の1または0を用いて表すことができる.1 bitには2つの値:0と1があり、falseとtrueを表すのにちょうど使用できます.
「データが存在するか否か」を判断するシーンでは、HashMapを用いて記憶するのが一般的であるが、hashmapというデータ構造KEYとValueの保存にはメモリを多く消費する必要があり、より多くのデータを保存するのに適していない.例えば、上記の問題では、ハッシュテーブルを用いてint型のkeyとboolean型のvalueを1レコードごとに保存すると、1レコードごとに少なくとも4バイトが必要となる.40億件のデータがすべて異なると仮定すると、40億件の記録が160億バイトを占め、16 Gメモリが必要で、明らかに高すぎる.
どのようにデータの占有する記憶空間を減らすかはビットマップを使って解決することができて、java.util.BitSetはビット単位で記憶することができ、BitMapの典型的な実装を提供する.
例えば、数字の山があり、記憶する必要があり、source=[3,5,6,9]はintで4*4バイト必要です.java.util.BitSetはtrue/falseを保存できます.Javaを使うならutil.BitSetは、かなり少なくなりますが、その原理は:1、まずデータの中の最大値maxvalue=92を探し出して、BitSet bsを宣言して、そのsizeはmaxvalue+1=103で、データsourceを遍歴して、bs[source[i]]はtrueに設定.最後の値は、(0はfalse、1はtrue)bs[0,0,0,1,0,1,0,1]3,5,6,9というint型で4バイトの32ビットを占める数字が1ビットしか使われていないため、大きなスペースが省けます.
一般的なアプリケーションシーンは、ログ分析、ユーザー数統計など、大量のデータを統計する必要がある場合です.統計40億個のデータに出ていないデータを40億個並べ替えるなどした.
三、BitSetの応用方法
BitSetはVectorインタフェースを実現し、BitSetでは配列サイズが必要に応じて増加し、ビットの値はブール型であり、bitSet内部はlong[]配列で実現されるため、初期サイズは64 bitであり、初期値はいずれも「false」である.
まずAPIの説明を見てみましょうBitSetクラスは必要に応じて増加するビットベクトル、Each component of the bit set has a boolean valueを実現した.各要素にはboolean値があり、The bits of a BitSet are indexed by nonnegative integers.非負の整数で各ビットをインデックス、Individual indexed bits can be examined,set,or cleared.インデックスに組み込まれた各ビットをテスト、設定、またはクリアできます.One BitSet may be used to modify the contents of another BitSet through logical AND, logical inclusive OR, and logical exclusive OR operations.論理的、論理的、または論理的異種または動作により、あるBitSetを使用して別のBitSetの内容を変更することができる.
By default, all bits in the set initially have the value false.デフォルトでは、set内のすべてのビットの初期値はfalseです.
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.各ビットsetには、現在使用されている空間のビット数である現在のサイズがあります.なお、このサイズはビットsetの実装に関係するため、実装によって変更される可能性がある.ビットsetの長さは、ビットsetの論理長に関係し、実装に関係なく定義される.
最大40億個のランダムに配列された32ビットの整数を含むシーケンスファイルを指定し、ファイルにない32ビットの整数を見つけます(ファイルには少なくともこのような数が欠けています.なぜですか).十分なメモリがある場合、この問題を解決するにはどうすればいいですか?(プログラミング珠玉)
二、BitMapを応用してビッグデータを保存する
データの存在性はbitビット上の1または0を用いて表すことができる.1 bitには2つの値:0と1があり、falseとtrueを表すのにちょうど使用できます.
「データが存在するか否か」を判断するシーンでは、HashMapを用いて記憶するのが一般的であるが、hashmapというデータ構造KEYとValueの保存にはメモリを多く消費する必要があり、より多くのデータを保存するのに適していない.例えば、上記の問題では、ハッシュテーブルを用いてint型のkeyとboolean型のvalueを1レコードごとに保存すると、1レコードごとに少なくとも4バイトが必要となる.40億件のデータがすべて異なると仮定すると、40億件の記録が160億バイトを占め、16 Gメモリが必要で、明らかに高すぎる.
どのようにデータの占有する記憶空間を減らすかはビットマップを使って解決することができて、java.util.BitSetはビット単位で記憶することができ、BitMapの典型的な実装を提供する.
例えば、数字の山があり、記憶する必要があり、source=[3,5,6,9]はintで4*4バイト必要です.java.util.BitSetはtrue/falseを保存できます.Javaを使うならutil.BitSetは、かなり少なくなりますが、その原理は:1、まずデータの中の最大値maxvalue=92を探し出して、BitSet bsを宣言して、そのsizeはmaxvalue+1=103で、データsourceを遍歴して、bs[source[i]]はtrueに設定.最後の値は、(0はfalse、1はtrue)bs[0,0,0,1,0,1,0,1]3,5,6,9というint型で4バイトの32ビットを占める数字が1ビットしか使われていないため、大きなスペースが省けます.
一般的なアプリケーションシーンは、ログ分析、ユーザー数統計など、大量のデータを統計する必要がある場合です.統計40億個のデータに出ていないデータを40億個並べ替えるなどした.
三、BitSetの応用方法
BitSetはVectorインタフェースを実現し、BitSetでは配列サイズが必要に応じて増加し、ビットの値はブール型であり、bitSet内部はlong[]配列で実現されるため、初期サイズは64 bitであり、初期値はいずれも「false」である.
まずAPIの説明を見てみましょうBitSetクラスは必要に応じて増加するビットベクトル、Each component of the bit set has a boolean valueを実現した.各要素にはboolean値があり、The bits of a BitSet are indexed by nonnegative integers.非負の整数で各ビットをインデックス、Individual indexed bits can be examined,set,or cleared.インデックスに組み込まれた各ビットをテスト、設定、またはクリアできます.One BitSet may be used to modify the contents of another BitSet through logical AND, logical inclusive OR, and logical exclusive OR operations.論理的、論理的、または論理的異種または動作により、あるBitSetを使用して別のBitSetの内容を変更することができる.
By default, all bits in the set initially have the value false.デフォルトでは、set内のすべてのビットの初期値はfalseです.
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.各ビットsetには、現在使用されている空間のビット数である現在のサイズがあります.なお、このサイズはビットsetの実装に関係するため、実装によって変更される可能性がある.ビットsetの長さは、ビットsetの論理長に関係し、実装に関係なく定義される.
public static void main(String[] args) {
int [] array = new int [] {1,2,3,22,0,3};
BitSet bitSet = new BitSet(6);
// bitmap
for(int i=0;i