3

なんらかの形式のデータ構造に格納する必要がある約 1,000,000 個のオブジェクトがあります。それらはキー (ID) によって一意である必要がありますが、日付に従って並べ替えられます。したがって、それらを何らかの形式のデータ構造に格納する最良の方法を考えようとしています。パフォーマンス (実行にかかる時間) が主な目標であり、次にメモリ使用量です。私の考えは、オブジェクトをツリーに配置することでした。オブジェクトがデータ構造に入るときに日付に従ってソートされる可能性があり、それらを順番に返すことができます。ただし、IDに基づいて単一のオブジェクトを見つけるのは非常に遅くなると思います。私が思いついたことの 1 つは、ID を日付にリンクする二次構造を作成して、単一のオブジェクトを見つけるのにかかる時間を短縮できるようにすることでした。

キーポイント：

オブジェクトは後で追加される可能性があるため、c.1,000,000 オブジェクトは修正されません。それらは更新または削除されません。Java のビルトイン Comparator は使用できません。データを返す効率を最適化しています - これが (日付順の) 完全なセットであるか、ID から取得された単一のオブジェクトであるかに関係なく。

4

2 に答える 2

3

メモリ使用量よりもパフォーマンスが重要な場合は、次の 2 つのデータ構造を使用します。

ArrayList<YourClass> instancesByDate;

と

HashMap<SomeId,YourClass> instancesById;

これにより、日付と O(1) ルックアップによる最速のトラバーサルが得られます (明らかに hashCode() に依存します)。

于 2013-03-02T10:14:23.283 に答える
0

ID ルックアップに ID => yourobject のハッシュテーブルを使用し、(ある程度の粒度で) 日付のセカンダリ ハッシュテーブルを使用するのはどうVector<yourobject>でしょうか。日付の「粒度」を選択して、各ベクトルに適度な数のオブジェクトを確保し、それぞれを日付で並べ替えることができます。

于 2013-03-02T10:09:52.127 に答える