Re: priority queue
On Sun, 29 Mar 2009, Andreas Leitgeb wrote:
Patricia Shanahan <pats@acm.org> wrote:
sara wrote:
I want to create a PriorityQueue pq which contains vectors of integers
and the priority is based on the size of the vector representing each
member. The declaration is as following:
The obvious solution is to remove and add each changed item.
That would mess up iterating over the queue, so I would keep a separate
set containing the same items, ...
for(Vector<Integer> v : setOfVectors){
if(v != headVector){
Good advice - an identical Vector could have been added twice.
By the way: it is better to replace "Vector" by "ArrayList"!
if(v.removeAll(headVector){
pq.remove(v);
pq.add(v);
Removing and adding an element is quite inefficient with priority queues:
removing means replacing the element by the last one and rolling that
back down to re-establish the heap-properties, and adding means appending
the new element at the end and rolling it up till the heap is fine.
True. Another way of doing this would be to do the removes in the for loop
(using Iterator.remove()), and then accumulate vectors to be re-added in a
side list; after the for loop, do an addAll to put the side list back into
the priority queue. My assumptions there are that (a) Iterator.remove() is
more efficient than PriorityQueue.remove() and (b) the addAll is more
efficient than a series of adds, although both of those are aspirations
rather than certainties.
This would also avoid the need to have the set which is a copy of the
priority list.
That explanation isn't very clear, so here's some code:
PriorityQueue<List<Integer>> pq;
Iterator<List<Integer>> it = pq.iterator();
List<Integer> head = pq.poll();
Collection<List<Integer>> toBeReAdded = new ArrayList<List<Integer>>();
while (it.hasNext()) {
List<Integer> vec = it.next();
if (vec.removeAll(head)) {
it.remove();
toBeReAdded.add(vec);
}
}
pq.addAll(toBeReAdded);
I wonder if there's an even cleverer approach using bitsets and/or an
inverted index, though.
Last time I had to do immediately subsequent remove&add operation, I
copied the PriorityQueue-source into my own package, and added a
replace-method, that would add the new element at the spot of the old
one and from there on roll it into its final place.
Back then I also posted this here, but no one seemed interested.
Awww, poor Andreas! :)
I'm thinking about starting a home for stray datastructures, such as my
GettableHashSet:
http://urchin.earth.li/~twic/GettableSet/
To be joined by the TreeList (O(log n) remove()!) i'm currently very
slowly working on. Maybe it can go there.
Furthermore, it surely pays to watch the vector's length before and
after the .removeAll(...) and do the re-queueing only if it really
changed.
That's why Patricia is making the remove/add predicate on the return value
of removeAll - removeAll returns true if the list was changed by the call,
and false if it wasn't.
Besides, I wonder, if the PQ's iterator supports removing and adding
elements without a concurrent modification exception. Is there a
general rule about iterator.add(...) in sorted Collections (i.e. where
the new element is likely added somewhere else than at the iterator
position)?
The decision about when to throw a ConcurrentModificationException is left
to the concrete class, rather than being specified in the collection
interface. PriorityQueue's iterator() method says:
Returns an iterator over the elements in this queue. The iterator does
not return the elements in any particular order.
Which means that this isn't a sorted collection in the sense you mean, but
says nothing about there being or not being any fail-fast behaviour.
tom
--
The future will accost us with boob-slapping ferocity. -- H. G. Wells