java - タイムスタンプ付きオブジェクトのリストを保持するデータ構造

Question

タイムスタンプ付きオブジェクトのリストがあり、実行する必要がある唯一のクエリは、「x より大きい timsetamp を持つすべてのオブジェクトを検索する」ことです。上記のルックアップを最適化するには、どのデータ構造が最適ですか? 挿入時間を長くしても問題ありませんが、可能であれば完全な EPL 実装は避けたいと考えています。

Answer 1

アプリケーションのどこかで SQL データベースを使用している場合は、タイムスタンプ フィールドのインデックスを作成し、クエリを作成します。

それ以外の場合、データベースがない場合、これはTreeMapまたはConcurrentSkipListのいずれかのジョブのように見えます。どちらもNavigableMap インターフェイスからsubMap(K, K)、headMap(K)、およびtailMap(K)メソッドを実装します。キーにComparableインターフェイスを実装するか、コレクションの作成時にComparatorを指定することにより、SortedMap (およびそのサブインターフェイス) のカスタム順序を指定できます。キーと値のマッピングが必要ない場合は、単にNavigableSetとその実装TreeSetまたはConcurrentSkipListSetを使用することもできます。

Answer 2

BST (二分探索木) はどうですか? InOrder は、O(logn) を使用して、必要なものを正確に提供します。

Answer 3

次のようなコードを使用できます。

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

}