Java найти ближайшее (или равное) значение в коллекции - PullRequest
Новая
       33

Java найти ближайшее (или равное) значение в коллекции

6 голосов
/ 10 мая 2011

У меня есть класс по линии: 

public class Observation {
   private String time;
   private double x;
   private double y;

   //Constructors + Setters + Getters
}

Я могу выбрать для хранения этих объектов в любом типе коллекции (Стандартный класс или третье лицо, например, Гуава). Я сохранил некоторые примерные данные в 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 Я хочу третье наблюдение.

Я, очевидно, могу перебирать коллекцию, пока не найду нужное время, но мне нужно делать это часто, и в конце дня у меня могут быть миллионы наблюдений, поэтому мне нужно найти решение, где я может найти соответствующие наблюдения эффективным способом.

Я рассмотрел различные типы коллекций, в том числе те, в которых я могу фильтровать коллекции с помощью Predicates, но мне не удалось найти решение, которое возвратило бы одно значение, в отличие от подмножества коллекции, которое удовлетворяет "< = "- состояние. По сути, я ищу SQL эквивалент SELECT * FROM ol WHERE time <= t LIMIT 1.

Я уверен, что есть разумный и простой способ решить мою проблему, поэтому я надеюсь быть просветленным. Заранее спасибо.

Ответы [ 4 ]

10 голосов
/ 10 мая 2011

Попробуйте TreeSet, предоставляющий компаратор, который сравнивает время. Он содержит упорядоченный набор, и вы можете запросить TreeSet.floor(E), чтобы найти наибольшую мин. У вас также есть headSet и tailSet для упорядоченных подмножеств.

Время добавления (извлечения) составляет O (log n). Я думаю, что очень подходит для ваших нужд.

Если вы предпочитаете карту, вы можете использовать TreeMap с похожими методами.

4 голосов
/ 10 мая 2011

Имейте класс Observation, реализующий Comparable и используйте TreeSet для хранения объектов, которые сохранят элементы отсортированными. TreeSet реализует SortedSet, поэтому вы можете использовать headSet или tailSet, чтобы получить представление о наборе до или после искомого элемента. Используйте метод first или last в возвращенном наборе, чтобы получить искомый элемент.

Если вы застряли на ArrayList, но можете самостоятельно сортировать элементы, используйте Collections.binarySearch для поиска элемента. Возвращает положительное число, если точный элемент найден, или отрицательное число, которое можно использовать для определения ближайшего элемента. http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20java.lang.Object)

3 голосов
/ 10 мая 2011

Сортируйте вашу коллекцию (ArrayList, вероятно, будет работать здесь лучше всего) и используйте BinarySearch , который возвращает целочисленный индекс совпадения «ближайшего» возможного совпадения, т. Е. Возвращает ...

индекс ключа поиска, если он содержится в списке; в противном случае (- (точка вставки) - 1). Точка вставки определяется как точка, в которой ключ будет вставлен в список: индекс первого элемента больше, чем ключ, или list.size (),

1 голос
/ 10 мая 2011

Если вам посчастливилось использовать Java 6, и производительность SortedSet для вас не имеет большого значения. Взгляните на методы TreeSet ceiling, floor, higher и lower.

...