Java在集合中查找最接近(或相等)的值

Question

我有一个类:

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.

现在来问题了.我经常需要找到一个time等于或接近一定时间的一(1)个观测值,例如,如果我的时间是08:01:29我想在示例数据中获取第四个观测值,并且如果时间是08:01:27我想要第三个观测值.

我显然可以遍历整个集合,直到找到我正在寻找的时间,但我需要经常这样做,并且在一天结束时我可能有数百万的观察,所以我需要找到一个解决方案,我可以找到有效的相关观察.

我已经查看了各种集合类型,包括我可以过滤集合的类型,Predicates但是我找不到可以返回一个值的解决方案,而不是满足"<="条件的集合的子集.我基本上是在寻找SQL的等价物SELECT * FROM ol WHERE time <= t LIMIT 1.

我相信有一个聪明而简单的方法来解决我的问题所以我希望能够开悟.先感谢您.

Answer 1

尝试使用TreeSet提供比较时间的比较器.它保留了一个有序的集合,你可以要求TreeSet.floor(E)找到最大的最小值(你应该提供一个假观察与你正在寻找的时间).您还可以为有序子集设置headSet和tailSet.

它有O(log n)时间用于添加和检索.我认为非常适合您的需求.

如果您更喜欢Map,则可以使用具有类似方法的TreeMap.