C++ to Java :Эффективный поиск в коллекции
Имея в основном опыт работы с C++, я сейчас в гневе пишу Java. Что-то, что я нахожу базовым в C++ с использованием STL, кажется более громоздким в Java, чем я думаю, что должно быть. Я пришел к выводу, что, вероятно, есть лучшая идиома Java, которую я еще не понял. Вот пример использования псевдокода -.
У меня есть набор вещей, которые имеют естественное отношение упорядочения, основанное на некоторых переменных-членах, которые оказываются строками.
class Thing
{
String key1;
String key2;
}
В C++ я мог бы определить оператор упорядочения
///
/// @brief
/// provide a total order for 'Things' using key1 and key2
///
bool operator<(const Thing& a, const Thing& b)
{
if (a.key1 < b.key1) return true;
else if (a.key1 > b.key1) return false;
else return a.key2 < b.key2;
}
Затем я могу найти элементы за O (log N )раз, используя set ::find для случая наличия Вещи. Использование дополнительных перегрузок operator
struct Ordering
{
/// A strict weak ordering not a total ordering
bool operator()(const Thing& A,const std::string& key1) const;
}
const_iterator iter = std::lower_bound(someThings.begin(),
someThings.end(),
key1,
Ordering());
Чтобы сделать это менее абстрактным, представьте, что key1 — это имя, а key2 — это версия. Я могу спросить, есть ли у нас какое-либо программное обеспечение под названием Foobar или, точнее, у нас есть Foobar v1.0.
На первый взгляд, самым прямым эквивалентом набора std ::в Java является TreeSet. Порядок может быть реализован путем подкласса интерфейса Comparator. Однако для того, о чем я говорю, похоже, что для этого на Java потребуется несколько карт. В С++ нужно было бы использовать ассоциативный контейнер, такой как карта std ::, только если бы я хотел изменить значение. В наборе C++ std ::, как и в Java TreeSet, значением является собственный ключ. Однако в C++ я могу написать компараторы для сравнения «Thing» со «std ::string», используя key1 или key2 в зависимости от ситуации, и найти конкретную вещь в их стандартном ::наборе.Мне кажется, что вам нужно использовать Map, чтобы сделать это на Java. В противном случае (, поскольку Comparator имеет только один параметр типа ). вы получите беспорядок, как:
public static class Order implements ComparatorОднако, если вы сделаете это, вы можете (в классе Thing )написать:
Set things = new TreeSet(new Order());
boolean hasFieldWithKey1(final String key1)
{
return this.fields.contains(key1);
}
с набором Java вы можете только проверить существование, но не получить объект, который вы ищете. например. ты не можешь сделать
Field getFieldWithKey1(final String key1)
{
return this.fields.floor(key1);
}
потому что такие методы, как floor (), принимают только объекты типа значения (, т. е. Thing )
. Очевидным решением является использование карты для каждого ключа.
Map thingsByKey1 = new TreeMap(new Order());
Исходя из фона C++, это кажется излишне раздутым. Почему я должен снова хранить ключ, если он уже содержится? Если у меня два ключа, то еще хуже. Мне понадобятся две карты.
Map thingsByKey1 = new TreeMap(new OrderByKey1());
Map thingsByKey2 = new TreeMap(new OrderByKey2());
Теперь я дублирую не только ключ, но и создаю дополнительные ненужные древовидные структуры данных (или HashMaps с лучшей производительностью во время выполнения ). Для реализации упорядочения, как указано выше, это также может быть «просто неправильным», поскольку сама по себе каждая клавиша формирует только частичный порядок, а не полный порядок в наборе вещей.
Я видел здесь ответы на вопросы о поиске с использованием линейного поиска, который почти всегда является худшим выбором. Например.
Поиск всех объектов с заданным свойством внутри коллекции
Я отмечаю, что существует версия BinarySearch, которая принимает объект Comparator в качестве аргумента, но возвращает ему индекс элемента, а не сам элемент. Это означает, что существует ненужный вызов для получения ()после его использования (при условии, что коллекция поддерживает его ).
Так как же Java делает это эффективно и во времени, и в пространстве?