#java #collections #find #predicate
#java #Коллекции #Найти #предикат
Вопрос:
У меня есть класс, похожий на:
public class Observation {
private String time;
private double x;
private double y;
//Constructors Setters Getters
}
Я могу выбрать хранение этих объектов в любом типе коллекции (стандартный класс или сторонний, например Guava). Я сохранил некоторые примеры данных в приведенном ниже ArrayList, но, как я уже сказал, я открыт для любого другого типа коллекции, который будет делать трюк. Итак, несколько примеров данных:
ArrayList<Observation> ol = new ArrayList<Observation>();
ol.add(new Observation("08:01:23",2.87,3.23));
ol.add(new Observation("08:01:27",2.96,3.17));
ol.add(new Observation("08:01:27",2.93,3.20));
ol.add(new Observation("08:01:28",2.93,3.21));
ol.add(new Observation("08:01:30",2.91,3.23));
В примере предполагается соответствующий конструктор в Observation . Временные метки хранятся как String объекты, поскольку я получаю их как таковые из внешнего источника, но я рад преобразовать их во что-то другое. Я получаю наблюдения в хронологическом порядке, чтобы я мог создавать отсортированную коллекцию наблюдений и полагаться на нее. Временные метки не уникальны (как видно из примера данных), поэтому я не могу создать уникальный ключ на основе time .
Теперь к проблеме. Мне часто нужно найти одно (1) наблюдение с time равным или ближайшим к определенному времени, например, если мое время было 08:01:29 , я хотел бы получить 4-е наблюдение в данных примера, и если время 08:01:27 равно, я хочу 3-е наблюдение.
Очевидно, я могу перебирать коллекцию, пока не найду время, которое я ищу, но мне нужно делать это часто, и в конце дня у меня могут быть миллионы наблюдений, поэтому мне нужно найти решение, в котором я мог бы эффективно находить соответствующие наблюдения.
Я просмотрел различные типы коллекций, включая те, с помощью которых я могу фильтровать коллекции Predicates , но мне не удалось найти решение, которое возвращало бы одно значение, в отличие от подмножества коллекции, которое удовлетворяет условию «<=». По сути, я ищу SQL-эквивалент SELECT * FROM ol WHERE time <= t LIMIT 1 .
Я уверен, что есть умный и простой способ решить мою проблему, поэтому я надеюсь, что меня просветят. Заранее благодарю вас.
Ответ №1:
Попробуйте TreeSet, предоставляющий компаратор, который сравнивает время. Он содержит упорядоченный набор, и вы можете запросить TreeSet.floor(E) найти наибольшее минимальное значение (вы должны предоставить фиктивное наблюдение со временем, которое вы ищете). У вас также есть гарнитура и хвостовой набор для упорядоченных подмножеств.
У него есть O (log n) времени для добавления и извлечения. Я думаю, что это очень подходит для ваших нужд.
Если вы предпочитаете карту, вы можете использовать древовидную карту с аналогичными методами.
Комментарии:
1. Спасибо. Это, безусловно, сделало свое дело. Я пошел с картой дерева и использую
timeв качестве ключа. Кроме того, мне пришлось немного настроить компаратор, чтобы разрешить неуникальное время в качестве ключей. Спасибо.2. Отлично. Но какой ключ вы используете? (или вы используете компаратор, который сравнивает время и «что-то большее»?)
3. Я использую
timeв строковом формате в качестве ключа и реализую компаратор, который оценивает ключи и всегда возвращает -1 или 1, даже если ключи идентичны, чтобы иметь возможность поддерживать полный набор в TreeMap, даже если ключи не уникальны. Могут быть другие способы, которыми я мог бы этого достичь (?), Но это работает, что является самым важным.4. Я беспокоился, потому что я думаю, что несоответствующий порядок (я имею в виду: компаратор, который может возвращать a<b и b<a в зависимости от того, как вы его вызываете) может вызвать проблемы с map / set. Если это так, я предлагаю простое решение: вам нужен общий заказ (a! = b для каждого элемента), чтобы вы могли сначала сравнить время, а затем координаты. Я понимаю, что у вас не будет равных значений для всех свойств наблюдения 🙂 Если это не так, то объект наблюдения мог бы иметь частный идентификатор, инициализированный из a
private static AtomicInteger counterследующим образом:counter.incrementAndGet. Таким образом, вы всегда могли сравнить id…5. Вы абсолютно правы. Хотя решение, которое я создал с помощью TreeMaps и измененных компараторов, предоставило мне наблюдения, которые я искал, я понимаю вашу точку зрения о недостаточной надежности. В соответствии с вашим предложением я переработал решение с помощью счетчика, который я добавил к наблюдениям, а затем основал компаратор на сочетании времени / счетчика, плюс я сохраняю наблюдения в наборе деревьев. Сейчас я провожу некоторое тестирование, но, похоже, с первых появлений все работает нормально. Большое спасибо.
Ответ №2:
Отсортируйте свою коллекцию (ArrayList, вероятно, будет работать здесь лучше всего) и используйте BinarySearch, который возвращает целочисленный индекс либо совпадения с «ближайшим» возможным совпадением, т. Е. он возвращает…
индекс ключа поиска, если он содержится в списке; в противном случае, (-(точка вставки) — 1). Точка вставки определяется как точка, в которой ключ будет вставлен в список: индекс первого элемента, больший, чем ключ, или list.size(),
Ответ №3:
Реализуйте Observation класс Comparable и используйте TreeSet для хранения объектов, которые будут сохранять элементы отсортированными. TreeSet реализует SortedSet , так что вы можете использовать headSet или tailSet , чтобы получить представление о наборе до или после элемента, который вы ищете. Используйте метод first or last в возвращаемом наборе, чтобы получить элемент, который вы ищете.
Если вы застряли с ArrayList , но можете самостоятельно отсортировать элементы, используйте Collections.binarySearch для поиска элемента. Возвращает положительное число, если найден точный элемент, или отрицательное число, которое может быть использовано для определения ближайшего элемента. http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.Список, java.lang.Объект)
Ответ №4:
Если вам достаточно повезло использовать Java 6, и затраты на производительность, связанные с сохранением SortedSet , для вас не имеют большого значения. Взгляните на TreeSet ceiling , floor , higher и lower методы.