整数のコレクションを取り、コレクションから重複を削除する関数を書きたいと思います。ソートアルゴリズムを適用できません。同様に、コレクションを複製することはできません。メモリを節約し、バッテリーを大幅に使いすぎずに何百万ものアイテムを処理できる効率的なソリューションを提供する必要があります。
質問する
178 次
1 に答える
1
メモリが非常に不足している場合、最初から冗長な整数をリストに含めないことが最善の解決策です。これを行うには、ブール値の配列 [0..65536] を使用できます (8 x 8 を「パック」して小さくすることができます)。これは、既に使用されているものを記録します。
別の解決策は、項目を適切な場所に挿入することによってリストをソートすることですが、項目が既にここにある場合は挿入しません。挿入は各アイテムのログ (これまでの一意のアイテムの数) になるため、リストの *log(n) 時間のようなものになるはずです。
ソースを制御できない場合でも、必要に応じてより大きなブール値の配列を使用して、初期化することができます (すべてを false に設定してから、: isUsed[itemList[i]] = true;)。リストを破棄してメモリを再び確保し、配列から新しいリストを作成できます。したがって、出力は順序付けられます。
整数が 32 ビットの場合、配列は 500 MB の大きさになるため、大きすぎる可能性があります... しかし、整数の分布によっては(可能な数値の範囲は広いですか??)、そのサイズを下げることができる場合があります。 ...
メモリが非常に不足している場合は、オブジェクト プールを使用してオブジェクトを再利用できることに注意してください。
(リストから削除したばかりのオブジェクトを再利用することもできます。)
于 2012-12-29T18:41:09.543 に答える