Java: Каков наилучший способ найти элементы в отсортированном списке?

Question

у меня есть

List<Cat>

отсортировано по дням рождения кошек. Существует ли эффективный способ сбора коллекций Java всех кошек , которые родились 24 января 1983 года? Или какой подход в целом хорош?

Answer 1

Collections.binarySearch().

Если предположить, что кошки отсортированы по дню рождения, это даст индекс одной из кошек с правильным днем ​​рождения. Оттуда вы можете перебирать вперед и назад, пока не достигнете одного с другим днем ​​рождения.

Если список длинный и / или не многие кошки делят день рождения, это должно стать значительным выигрышем по сравнению с прямой итерацией.

Вот код, о котором я думаю. Обратите внимание, что я предполагаю список произвольного доступа ; для связанного списка, вы в значительной степени застряли с итерацией. (Спасибо 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;

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

Коллекции Google могут делать то, что вы хотите, используя Предикат и создавая отфильтрованную коллекцию, в которой предикат соответствует датам.

Answer 4

Если вам нужен действительно быстрый поиск, используйте HashMap с днем ​​рождения в качестве ключа. Если вам нужно отсортировать ключи, используйте TreeMap.

Поскольку вы хотите, чтобы у нескольких кошек был один и тот же день рождения, вам необходимо использовать коллекцию в качестве значения в Hast / TreeMap, например,

      Map<Date,Collection<Cat>>

Answer 5

Если вы каким-то образом не проиндексировали коллекцию по дате, единственным способом было бы перебрать все из них