CODEWITHSUNDEEP
javaalgorithmsearchsorting
cidadao
cidadao

Reputation: 1463

Search algorithm (with a sort algorithm already implemented)

Im doing a Java application and Im facing some doubts in which concerns performance.

I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated with a Entity.

The size of that priorityqueue could be huge and very frequently I will have to remove events associated to an entity.

Right now Im using an iterator to run all the priorityqueue. However Im finding it heavy and I wonder if there are better alternatives to search and remove events associated with an entity "xpto".

Any suggestions?

Thanks!

Upvotes: 3

Views: 414

Answers (5)

Keith Randall
Keith Randall

Reputation: 23265

It sounds like you need to implement a souped-up priority queue. In particular, you need O(logN) removal time. You can do this by keeping two data structures, an array of Events which is basically the binary heap storing your priority queue, and a HashMap from Event to the offset of that Event in the array (or maybe from Entity to a list of offsets of Events in that array).

You can then do normal heap operations as you would for a priority queue, you just need to update the hash map mappings every time an Event is moved. To remove an Event, look up the index of that event in the hash table and do a remove operation on the heap starting at that index.

Upvotes: 0

Christopher Barber
Christopher Barber

Reputation: 2678

A couple of ideas:

  1. Implement your priority queue using a treap ordered by the entity's key. If the keys are randomly distributed then you should be able to remove elements in O(log n) time.
  2. Maintain a separate mapping of Entity to Events currently in the queue. Instead of actually removing events from the queue immediately, just flip a bit on the Event object indicating it should be ignored when it reaches the front of the queue.

Upvotes: 1

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297195

I'd suggest you make a class composed of a PriorityQueue and a Set, with the following operations:

  • To add an element, remove it from the Set and, if it weren't there, add it to the PriorityQueue.
  • To remove an element, add it to the Set.
  • To unqueue an element, unqueue elements from the PriorityQueue until the unqueued element is not present in the Set. Remove any unqueued elements from the Set.

Upvotes: 0

Doug Currie
Doug Currie

Reputation: 41180

Since remove is a linear time operation, you are getting O(N*N) performance.

If you subclass PriorityQueue and create a new method (named removeIf perhaps) that combines the iterator and remove methods then you could reduce this to O(N log(N)).

Upvotes: 0

Freiheit
Freiheit

Reputation: 8757

Theres a few options:

  1. Could you use separate queues for each entity? So when you get an event for "xpto" you put it into the XptoPriorityQueue? This will reduce the size of each queue, but could also lead to some other management issues.
  2. Are you removing events for a specific entity to process them sooner? If so then you should simply give those entities a higher priority and bump them to the top of the queue.
  3. Are you removing events for a specific entity to remove them from the queue and ignore them? If so then they should either never get into the queue or should get a lower priority.

Upvotes: 1

Related Questions