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

Question

我有一个类:

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

   //Constructors + Setters + Getters
}

我可以选择将这些对象存储在任何类型的集合中(标准类或第 3 方，如 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我想获取示例数据中的第 4 个观察值，如果时间是 08:01:27我想要第三次观察。

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

我查看了各种集合类型，包括可以使用 Predicates 过滤集合的类型但我没能找到一个解决方案来返回一个值，而不是满足“<=”条件的集合的子集。我本质上是在寻找 SELECT * FROM ol WHERE time <= t LIMIT 1 的 SQL 等效项.

我确信有一种聪明而简单的方法可以解决我的问题，所以我希望得到启发。提前谢谢你。

Answer 1

尝试 TreeSet 提供比较时间的比较器。它维护一个有序集，您可以请求 TreeSet.floor(E) 来找到最大的最小值(您应该提供一个包含您正在寻找的时间的虚拟观察)。您还有用于有序子集的 headSet 和 tailSet。

它有 O(log n) 时间用于添加和检索。我觉得很适合你的需求。

如果您更喜欢 Map，您可以使用类似方法的 TreeMap。