100 万の ID の大きな配列/リストがあり、使用できる最初の空き ID を見つける必要があります。このデータ構造を参照し、id を取り (その間は used とマークされます)、後でそれを返します ( free とマークされます)。どのようなデータ構造を使用できるか知りたいですか? そして、これを効率的に時間と空間で（別々に）行うために使用できるアルゴリズムは何ですか。ここに既に存在する場合はご容赦ください。投稿する前に検索しました。
質問する
358 次
6 に答える
6
単純ですが効率的な方法は、すべての ID をスタックに格納することです。ID の取得は一定時間の操作です: リストの最初の項目をポップします。タスクが終了したら、id をスタックにプッシュします。
最小の空き ID を返す必要がある場合 (空き ID ではありません)、最小ヒープを挿入して使用し、O(log N) で最小をポップできます。
于 2013-06-12T18:11:12.830 に答える
2
リンク リスト (ID のリンク リスト) を使用してみてください。これらすべてのリストをリンクすると、head は空きリストを指す必要があります (init ですべてが空きであるとしましょう)。使用済みとしてマークされるたびに、それを削除してリストの最後に配置し、ヘッドが次の空きリストを指すようにします。このようにして、リストは「無料から使用済みへ」という形で構造化されます。O(1) で空きリストを取得することもできます。また、ID がフリーとしてマークされている場合は、リンクされたリストの最初のメンバーとして配置します (フリーになると使用可能になります)。つまり、このリストを指すようにします。これが役立つことを願っています！
于 2013-06-12T18:16:45.640 に答える
0
最小の ID が厳密に必要でない場合は、ID を 1000 のバッチでモジュールに割り当てることができます。ID を解放するときは、リストの後ろに追加できます。また、ときどきリストを並べ替えて、割り当てた ID が最下位のものであることを確認します。
于 2013-06-12T22:08:43.160 に答える
0
プリアンブル: バイナリ ヒープは確かに最良の答えのようです。ここでは、いくつかのシナリオで利点がある代替案を紹介します。
考えられる方法の 1 つは、フェンウィック ツリーを使用することです。各位置に 0 または 1 を格納できます。これは、位置が既に使用されているかどうかを示します。そして、バイナリ検索で最初の空の位置を見つけることができます (合計 n-1 を持つ最初の範囲 [1..n] を見つけるため)。この操作の複雑さは O(log^2 n) で、バイナリ ヒープよりも悪いですが、このアプローチには別の利点があります。
- フェンウィック ツリーは 10 行未満のコードで実装できます
- O(log n) で範囲の密度 (使用された ID の数 / 合計 ID) を計算できるようになりました。
于 2013-06-12T20:37:39.733 に答える
-1
まあ、配列はおそらく最良の構造ではありません。ハッシュは、少なくとも速度的には優れています。各「ノード」の構造については、ID と、それが使用されているかどうかだけが必要であることがわかります。
于 2013-06-12T18:10:53.520 に答える