データ構造のビットマップ

2278 ワード

1. 概要
ビットマップ(bitmap)は非常に一般的な構造であり、インデックス、データ圧縮などの面で広く使われています.本稿はビットマップの実現方法とその応用シーンを紹介する.
2.ビットマップの実現
(1)自分で実現する
ビットマップでは、各要素は「0」または「1」であり、その対応する要素が存在しないまたは存在しないことを表しています.

#define INT_BITS sizeof(int)

#define SHIFT 5 // 2^5=32

#define MASK 0x1f // 2^5=32

#define MAX 1024*1024*1024 //max number

int bitmap[MAX / INT_BITS];

/*

*    i 

* i >> SHIFT     i / (2 ^ SHIFT),

* i&MASK   mod   m mod n   

*/

void set(int i) {

bitmap[i >> SHIFT] |= 1 << (i & MASK);

}

//   i 

int test(int i) {

return bitmap[i >> SHIFT] & (1 << (i & MASK));

}

//   i 

int clear(int i) {

return bitmap[i >> SHIFT] & ~(1 << (i & MASK));

}

(2)関数ライブラリの実現
C＋＋＋のSTLにはbitmapクラスがあり、多くの方法が提供されています.詳細は以下の通りです.http://www.cplusplus.com/reference/stl/bitset/
3. ビットマップの適用
3.1    列挙
(1)全グループ
文字列の全結合エニュメレーション(長さnの文字列に対して、組み合わせは2^n種)であり、例えばabcdefは、文字列からバイナリへのマッピング関係を構築し、エニュメレーションバイナリによって完全に並べ替えられます.
null-->000000
f——>000001
e——>000010
ef——>000011
……
abcedf——>111111
(2)ミルトン距離
エニュメレート・アルゴリズムは、複雑さはO(N^2)ですが、複雑さはどうやって低減されますか?
N個の二次元の点なら、どのように比較的早い方法で求められますか?
簡単な数学的変形によって,このような数学的公式を得ることができる.
観察によって,各ペアの同じ要素の符号は必ず反対であることが分かった.i-y_i,そこで、これらの二次元の点のx軸y軸の前の正負号を列挙するというバイナリ思想の考えがあります.これは0~3の数のバイナリ形式で各要素の前の正負号を表します.1は＋号、0は−号を表します.i-y_iです.このようにして、私たちは2^2*N回を通してこれらの2つのグループの異なる記号の数値を記録することができます.それぞれの2進数に対して表した異なる式は彼らの値を記録するだけでいいです.iとmin_iこれらの同じバイナリ表現の式子max_を出すi–min_i,最後にans=max{maxui-minui}を解くことができます.
ビットマップによって、アルゴリズムの時間複雑さはO(N)になり得る.
3.2 検索
剪定を設計する場合は、検索した履歴情報を保存する必要があります.ビットマップを使用して履歴情報データのスペースを減らすことができます.
3.3   圧縮
(1)     2.5億個の整数の中から重複しない整数を探し出して、注、メモリが不足しています.この2.5億個の整数を格納しますか?
(2)     テンセント面接の問題:40億個の重複しないunsigned intの整数をあげて、順序を並べていないで、それからもう一つの数をあげて、どのように速くこの数があの40億個の中にあるかどうかを判断しますか?
4.まとめ
Bitmapは非常に簡潔で高速なデータ構造であり、彼は証明書記憶空間と速度を最適化することができます.
5. 参考資料
(1)     《C実現bit mapビットマップ》:
http://blog.csdn.net/QIBAOYUAN/archive/2010/09/29/5914662.aspx
(2)     武森「浅談情報学競技における「0」と「1」
————————————————————————————————————————————————
もっと多いデータ構造とアルゴリズムについて紹介します.データ構造とアルゴリズムのまとめを見てください.
転載先:https://www.cnblogs.com/mycapple/archive/2012/08/07/2626908.html

大話のデータ構造の迅速なソート