Search algorithm (with a sort algorithm already implemented)

Question

Hello,

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!

Answer 1

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.

Answer 2

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)).

Answer 3

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.

Answer 4

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.

Answer 5

You can store an EventCollection(modelled using PriorityQueue) in a TreeMap (replacement for main PriorityQueue) instead of events.

The EventCollection will have events corresponding to the same entity.

The compare function of an EventCollection will be the compare function of the event you are already using. The events which you will use for compare will be the largest priority events in the collections you want to compare.

If you want to get highest pri event, you get the largest element in the TreeMap (I believe it supports that) and get the max event from there.

Update the collection (by removing that event) and then delete that collection entry from the TreeMap and reinsert into the TreeMap. I believe the TreeMap gives you the new position in the tree.

Now update an (entity->position in tree map) hashtable entry corresponding to that entity.

Anytime a new event comes in, check the (entity-position in tree map) hashtable and insert that event into the corresponding EventCollection and again update the collection (delete/insert) in the treemap and then update the hashtable with the new position.

If you want to delete all events of a particular entity, all you need to do is find the corresponding EventCollection and delete it from the TreeMap and the hashtable.

Since you can use a PriorityQueue to model the EventCollection class, you won't have to throw away your existing code.

Hope it works for you.

Answer 6

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.