3

マルチキーに基づいて、いくつかの値を非常に高速に見つける必要があります。キーは：で構成され < Int userId, String measureName, Date startDate, Date endDate > 、値はdoubleです。

問題は、日付範囲ではなく、日を示す値を要求する必要があることです。したがって、、、および日を要求する場合userId、measureNameデータ構造は、日がとの間である値で応答する必要がstartDateありendDateます（日付範囲の間に重複はありません）。

これを実装するのにどちらが優れたデータ構造であるか理解できません。HashMap？TreeMap？MultiKeyMap？RangeMap？ヘルプ！:)

4

4 に答える 4

3

TreeMapと次のようなメソッドを使用する必要があると思います： http：//docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#floorEntry（K ） http://docs.oracle.com/ javase / 6 / docs / api / java / util / TreeMap.html＃higherEntry（K） ただし、比較関数では1つの日付（startDateまたはendDate）のみを使用します。これらの範囲は重複しないため、これは問題にはならず、TreeMapの前述のメソッドを使用可能にします。

例：比較endDate（および他の日付を除く他のフィールド）で使用することにした場合は、メソッドを使用する必要がありますfloorEntry

于 2013-03-12T21:58:01.717 に答える
0

カスタム キー オブジェクトを使用した TreeMap が最適です。次のようなものがあります。

...
TreeMap<MyMultiKey,Double> map = ...

class MyMultiKey implements Comparable<MyMultiKey>{
...
}

マルチキーを適切に並べ替えるためにMyMultiKeyのメソッドが実装されていると仮定すると、 を使用して特定の日を検索するたびに新しいインスタンスを作成し、開始時刻と終了時刻がその日を含むキーを見つけたことを確認できます。新しいキー インスタンスで指定しました。compareToMyMultiKeymap.floorKey(MyMultiKey m)map.higherKey(MyMultiKey m)

于 2013-03-12T22:03:21.173 に答える
0

User/Measurement 部分キーの Map をお勧めします。値はタプル (日付範囲、floatval) のソートされた配列になります。この配列で、日を含む日付範囲のバイナリ検索を実行します。

于 2013-03-12T22:15:10.013 に答える
0

と の組み合わせはどうMapでしょListうか。マップには and の複合キーがuserIdありmeasureName、値は日付範囲と double のソート済みリストですvalue。

Map<Key,List<Entry>> data = new HashMap<>();
List<Entry> entries = data.get(new Key(userId, measureName));
int i = Collections.binarySearch(entries, new Entry(searchDate,searchDate, 0.0));
double value = i < 0 ? 0.0 : entries.get(i).value;

Keyは、そのメンバーとを実装hashCode()して使用する必要があります。一方の範囲が他方の範囲の一部である場合、0 を返さなければならない場所を実装する必要があります (startDate の比較が <= 0 で endDate の比較が >= 0 の場合、または startDate の比較が >= 0 で endDate の比較が <= 0 の場合は 0)。 (endDate-startDate)/2 (範囲の中央) double に関係なく。equals()userIdmeasureNameEntryComparable<Entry>compareTo()value

この構造をほとんど変更せずに読み取りを行う場合、高速になるはずです。比較は多用するとネイティブにコンパイルされます。関数が 1 人のユーザーとメジャーのみで機能する場合は、並べ替えられたリストのみを使用できます。1 人のユーザーのみで機能する場合は、 Map<UserId<Map<MeasureName,List<Entry>>>>代わりに like 構造を作成できます。

最初に簡単な解決策を試し、前後に測定し、必要な場合にのみパフォーマンスの最適化を行います。

于 2013-03-12T22:49:54.443 に答える