Java：ソートされたリスト内の要素を見つける最良の方法は何ですか？

Question

私は猫の誕生日でソート

List<Cat> 

を持っています。 1983年1月24日に生まれたすべての猫を見つけるための効率的なJava Collectionsの方法はありますか？あるいは、一般的にどのような良いアプローチですか？

Answer 1

Collections.binarySearch()。

猫が誕生日によってソートされていると仮定すると、正しい誕生日の猫のインデックスが表示されます。そこから、あなたは誕生日の異なる1つを押すまで前後に繰り返すことができます。

リストが長く、誕生日を共有していない猫が多い場合、これはストレート反復に比べて大きな勝利になるはずです。

ここに私が考えているコードの種類があります。私はrandom-accessのリストを仮定しています。リンクされたリストの場合、あなたはかなり反復に固執しています。 （コメントでこれを指摘してフレッド-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; 

Answer 2

バイナリ検索が行くための古典的な方法です。

説明：バイナリ検索を使用しています。具体的な方法はありません。アルゴリズムは次のとおりです。

//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 ]; 

Answer 3

あなたは何とか日付でコレクションのインデックスを作成しない限り、あなたは本当に速い検索と誕生日とHashMapを使用する必要がある場合は、唯一の方法は、それらのすべて

Answer 4

を反復処理することであろうキー。キーをソートする必要がある場合は、TreeMapを使用します。

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

 Map<Date,Collection<Cat>> 

Answer 5

Google Collections述語を使用して述語が日付に一致するフィルター処理されたコレクションを作成することによって、あなたがやりたいことができます。