6

私は

List<Cat>

猫の誕生日でソート。1983年1月24日に生まれたすべての猫を見つける効率的なJavaコレクションの方法はありますか？または、一般的に良いアプローチは何ですか？

4

5 に答える 5

9

Collections.binarySearch()。

猫が誕生日でソートされていると仮定すると、これにより、正しい誕生日の猫の1つのインデックスが得られます。そこから、別の誕生日の誕生日を迎えるまで、前後に繰り返すことができます。

リストが長い場合や、誕生日を共有する猫が少ない場合、これは単純な反復よりも重要な勝利になるはずです。

これが私が考えている種類のコードです。ランダムアクセスリストを想定していることに注意してください。リンクリストの場合、反復にかなり悩まされています。（コメントでこれを指摘してくれたfred-oに感謝します。）

List<Cat> cats = ...; // sorted by birthday
List<Cat> catsWithSameBirthday = new ArrayList<Cat>();
Cat key = new Cat();
key.setBirthday(...);
final int index = Collections.binarySearch(cats, key);
if (index < 0)
    return catsWithSameBirthday;
catsWithSameBirthday.add(cats.get(index));
// go backwards
for (int i = index-1; i > 0; i--) {
    if (cats.get(tmpIndex).getBirthday().equals(key.getBirthday()))
        catsWithSameBirthday.add(cats.get(tmpIndex));
    else
        break;
}
// go forwards
for (int i = index+1; i < cats.size(); i++) {
    if (cats.get(tmpIndex).getBirthday().equals(key.getBirthday()))
        catsWithSameBirthday.add(cats.get(tmpIndex));
    else
        break;
}
return catsWithSameBirthday;
于 2009-03-18T14:06:16.427 に答える
8

二分探索は、古典的な方法です。

明確化：二分探索を使用すると言いました。特に単一の方法ではありません。アルゴリズムは次のとおりです。

//pseudocode:

index = binarySearchToFindTheIndex(date);
if (index < 0) 
  // not found

start = index;
for (; start >= 0 && cats[start].date == date; --start);
end = index;
for (; end < cats.length && cats[end].date == date; ++end);

return cats[ start .. end ];
于 2009-03-18T14:06:21.777 に答える
1

非常に高速な検索が必要な場合は、誕生日をキーとして HashMap を使用します。キーをソートする必要がある場合は、TreeMap を使用します。

複数の猫に同じ誕生日を持たせたいので、コレクションを Hast/TreeMap の値として使用する必要があります。

      Map<Date,Collection<Cat>>
于 2009-03-18T14:12:34.617 に答える
-1

何らかの方法でコレクションを日付でインデックス付けしない限り、唯一の方法はそれらすべてを反復処理することです

于 2009-03-18T14:10:40.037 に答える