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 对象，但我很乐意将它们转换为其他东西。我按时间顺序收到观察结果，这样我就可以创建并依赖排序的观察结果集合。时间戳不是唯一的（如示例数据中所示），因此我无法基于时间创建唯一键。

现在来说说问题。我经常需要找到时间等于或最接近某个时间的一 (1) 个观察值，例如，如果我的时间是08:01:29，我想获取示例数据中的第四个观察结果，如果时间是 08:01:27 我想要第三个观察结果。

显然，我可以迭代集合，直到找到我正在寻找的时间，但我需要经常这样做，最终我可能会有数百万个观察结果，所以我需要找到一个解决方案，在其中可以找到有效地进行相关观察。

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

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

Answer 1

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

添加和检索的时间为 O(log n)。我认为非常适合您的需求。

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

Answer 2

对您的集合进行排序（ArrayList 在这里可能效果最好）并使用 BinarySearch 返回“最接近”可能匹配的整数索引，即它返回...

搜索关键字的索引（如果它包含在列表中）；否则，(-(插入点) - 1)。插入点定义为将键插入列表的点：大于键的第一个元素的索引，或list.size()，

Answer 3

让 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 ）

Answer 4

如果您足够幸运能够使用 Java 6，那么保留 SortedSet 的性能开销对您来说并不是什么大问题。看看 TreeSet ceiling、floor、higher 和 lower 方法。