CODEWITHSUNDEEP
javadata-structures
qwerty
qwerty

Reputation: 3869

Data structure to hold a list of timestamped objects

I have a list of timestamped objects and the only query I need to execute would be "find all objects with a timsetamp greater than x". Which data structure would be best suited to optimize the above lookup? I am fine with larger insertion times, but would prefer not to go with a full EPL implementation if possible.

Upvotes: 3

Views: 1617

Answers (4)

Rishabh Puri
Rishabh Puri

Reputation: 91

How about a BST (binary search tree ? InOrder gives you exactly what you need , with O(logn).

Upvotes: 0

Ron Teller
Ron Teller

Reputation: 1890

You can use any sorted data structure that allows binary search (if you don't care about insertion time), and for a given a X, perform a search (which takes O(logN) time) to find the first object with timestamp > X, because the data structure is ordered, all the objects in the data structure after this object also have timestamp > X.

Note that if you want to return a list of object from this query, it can't be done better than O(N)- you will either copy or delete O(N) times, as the number of objects that can be retrieved in this query in the general case is O(N).

Upvotes: 0

Lie Ryan
Lie Ryan

Reputation: 64837

If you are using an SQL database in your application somewhere, then create an index for the timestamp field and just make the query.

Otherwise if you don't have database, this looks like a job for either TreeMap or ConcurrentSkipList. Both implements the subMap(K, K), headMap(K), and tailMap(K) method from NavigableMap interface. You can specify a custom ordering for any SortedMap (and its subinterfaces) by implementing Comparable interface in your keys or by specifying Comparator when creating your collection. If you don't need to have key-value mapping, you can also simply use NavigableSet and their implementations TreeSet or ConcurrentSkipListSet.

Upvotes: 8

MaVRoSCy
MaVRoSCy

Reputation: 17839

You can use code like this:

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

}

Upvotes: 0

Related Questions