巨大なビットマップ

Question

インタビューの質問に最初のセットビットの検索：

を万台を保持することができ、駐車スロットでは、無料駐車スロットを見つける必要があります。スロットがどこにあるか、すなわち駐車場が複数の入口を有することができ、入口付近のスロットを見つけることなどは問題ではないという条件はない。問題は、どのような種類のデータ構造を使用すべきか、さまざまな操作の複雑さがどのようなものかということでした。

私は、撮影/空きスロットのために0/1で、百万ビットのビット配列を使用することを提案しました。フリースポットを見つけるために、最初のセットビットを見つけることに翻訳されました。そこに車が何台あるかについては何も想定しないでください。つまり、ビット配列が疎であるか密集している可能性があります。

巨大なビットマップのセットビットを見つける最も速い方法は何ですか？私はバイナリ検索+効率的なffs（）をスキームとして単語ごとに提案しました。

ストア変数の最後の空きスロットのインデックス、その後、最初からビットマップをスキャンしません。次の1を探しているが、この値から：

Answer 1

あなたはこの道を行くことができます。

スロットを解放する必要がある場合は、最後のインデックスに割り当てます。

std::vector<bool>をビット配列にすることができますので、ビットを自分で処理する必要はありません（boolは内部的にintにパックされています）。上位アレイにおける

``std::vector<bool>`` Bitmap; 
``std::vector<bool>`` Bitmap2; // half-sized 
``std::vector<bool>`` Bitmap4; // 1/4 
``std::vector<bool>`` Bitmap8; // 1/8 
// etc 

free

値が低レベルの配列は、任意の空きスロットを有する状況に対応する：

あなたがmip-mapped構造を導入することができます。バイナリ検索を使用してこの構造をトラバースすることができます。

Answer 2

32ビット整数は約4MBのメモリを必要とします。だから私は自由なスロットのリストを保持していると思います。車が入るたびに、あなたは項目をリストから取り出し、それを割り当てます。車が出るたびに、解放されたスロット番号をリストに入れます。

実際にはstackまたはLIFO構造体として使用されているので、これは空きスロットを見つけて返すために最適なO（1）パフォーマンスを提供します。スロットを解放状態にする。生のチャンクで低レベルでこれを行うと、リストの現在の終わりを示すポインタが必要になります。スロットを見つけると、そのポインタがデクリメントされ、その値が返されます。スロットを返すと、ポインタが割り当てられ、その後にインクリメントされます。

後で追加要件を追加する場合は、データの操作を行うことができます。それをheapに変換します。 0/1ビットの大きなマップでは、このような拡張は不可能です。