java - 保存时间戳对象列表的数据结构

Question

我有一个带时间戳的对象列表，我需要执行的唯一查询是“查找所有 timsetamp 大于 x 的对象”。哪种数据结构最适合优化上述查找？我可以接受更长的插入时间，但如果可能的话，我不希望使用完整的 EPL 实现。

Answer 1

如果您在应用程序的某处使用 SQL 数据库，则为时间戳字段创建索引并进行查询。

否则，如果您没有数据库，这看起来像是TreeMap或ConcurrentSkipList的工作。两者都实现了来自NavigableMap 接口的subMap(K, K)、headMap(K)和tailMap(K)方法。您可以通过在键中实现Comparable接口或在创建集合时指定Comparator来为任何 SortedMap（及其子接口）指定自定义排序。如果您不需要键值映射，您也可以简单地使用NavigableSet及其实现TreeSet或ConcurrentSkipListSet。

Answer 2

您可以使用任何允许二进制搜索的排序数据结构（如果您不关心插入时间），并且对于给定的 a X，执行搜索（这需要O(logN)时间）以找到第一个对象timestamp > X，因为数据结构是有序的，这个对象之后的数据结构中的所有对象也都有timestamp > X。

请注意，如果您想从此查询返回O(N)对象列表，最好的方法是- 您将复制或删除O(N)时间，因为在一般情况下可以在此查询中检索的对象数量是O(N).

Answer 3

BST（二叉搜索树）怎么样？InOrder 用 O(logn) 为你提供你所需要的东西。

Answer 4

你可以使用这样的代码：

//declare an ArrayList of Objects
ArrayList<MyTimestampedObject> list = loadObjects();

//new list to store Objects after condition check
ArrayList<MyTimestampedObject> newList = new ArrayList<MyTimestampedObject>();

//loop through the list
for(MyTimestampedObject tmp:list ){

  //check condition
  if(tmp.getDate()>x){
    //do something
    newList.add(tmp);
  }

}