Java finds closest (or equal) value in collection

Question

I have a class line by line:

public class Observation { private String time; private double x; private double y; //Constructors + Setters + Getters } 

I can choose to save these objects in any type of collection (standard class or a third-party, for example, Guava). I saved some example data in an ArrayList below, but as I said, I am open to any other type of collection that will do the trick. So, some examples of data:

 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)); 

The example uses the match constructor in Observation . Timestamps are saved as String objects, as I get them as such from an external source, but I'm happy to convert them to something else. I receive observations in chronological order so that I can create and rely on a sorted collection of observations. Timestamps are NOT unique (as can be seen from the example data), so I cannot create a unique key based on time .

Now to the problem. I often need to find one (1) observation with time equal to or closest to a certain time, for example, if my time was 08:01:29 , I would like to get the 4th observation in the example data and if the time is 08:01:27 need 3rd observation.

I can obviously go through the collection until I find the time I'm looking for, but I need to do it often, and at the end of the day I can have millions of observations, so I need to find a solution where I can efficiently find the relevant observations.

I looked at various types of collections, including those where I can filter collections using Predicates , but I was unable to find a solution that returns a single value, unlike a subset of the collection that executes the "<=" - state. I'm basically looking for the SQL equivalent SELECT * FROM ol WHERE time <= t LIMIT 1 .

I am sure there is a smart and easy way to solve my problem, so I hope to be enlightened. Thank you in advance.

Answer 1

Try TreeSet, providing a comparator that compares time. It maintains an ordered set, and you can query TreeSet.floor(E) to find the highest minimum (you must provide a dummy observation with the time you are looking for). You also have a headSet and tailSet for ordered subsets.

This is the O (log n) time to add and retrieve. I think this is very suitable for your needs.

If you prefer a Map, you can use TreeMap with similar methods.

Answer 2

Add the Observation class to Comparable and use the TreeSet to store objects that will preserve the sorting of elements. TreeSet implements a SortedSet , so you can use headSet or tailSet to get an idea of ​​the set before or after the item you are looking for. Use the first or last method for the returned set to get the item you are looking for.

If you are stuck in an ArrayList but can keep items sorted by yourself, use Collections.binarySearch to search for the item. It returns a positive number if an exact element is found, or a negative number that can be used to determine the nearest element. http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20java.lang.Object )

Answer 3

Sort your collection (ArrayList will probably work best here) and use BinarySearch , which returns an integer index or matches the “closest” possible match, i.e. returns ...

index of the search key, if it is contained in the list; otherwise (- (entry point) - 1). The insertion point is defined as the point at which the key will be inserted into the list: the index of the first element is larger than the key, or list.size (),

Answer 4

If you are fortunate enough to use Java 6, and the overhead of maintaining a SortedSet not very important to you. See the TreeSet ceiling , floor , higher and lower methods.