On Mon, Dec 10, 2007, Shai Erera wrote about "Performance
Improvement for
Search using PriorityQueue":
Hi
Lucene's PQ implements two methods: put (assumes the PQ has room
for the
object) and insert (checks whether the object can be inserted
etc.). The
implementation of insert() requires the application that uses
it to
allocate
a new object every time it calls insert. Specifically, it cannot
reuse
the
objects that were removed from the PQ.
I've read this entire thread, and would like to add my comments
about
three
independent issues, which I think that can and perhaps should be
considered
separately:
1. When Shai wanted to add the insertWithOverflow() method to
PriorityQueue
he couldn't just subclass PriorityQueue in his application, but
rather
was forced to modify PriorityQueue itself. Why? just because one
field
of that classi - "heap" - was defined "private" instead of
"protected".
Is there a special reason for that? If not, can we make the
trivial
change
to make PriorityQueue's fields protected, to allow Shai and
others (see
the
next point) to add functionality on top of PriorityQueue?
2. PriorityQueue, in addition to being used in about a dozen
places inside
Lucene, is also a public class that advanced users often find
useful
when
implementing features like new collectors, new queries, and so
on.
Unfortunately, my experience exactly matches Shai's: In the two
occasions
where I used a PriorityQueue, I found that I needed such a
insertWithOverflow() method. If this feature is so useful (I
can't
believe
that Shai and me are the only ones who found it useful), I
think it
would
be nice to add it to Lucene's PriorityQueue, even if it isn't
(yet) used
inside Lucene.
Just to make it sound more interesting, let me give you an
example where
I needed (and implemented) an "insertWithOverflow()": I was
implementing
a
faceted search capability over Lucene. It calculated a count for
each
facet value, and then I used a PriorityQueue to find the 10 best
values.
The problem is that I also needed an "other" aggregator, which
was
supposed
to aggregate (in various ways) all the facets except the 10 best
ones.
For
that, I needed to know which facets dropped off the
priorityqueue.
3. Finally, Shai asked for this new
PriorityQueue.insertWithOverflow()
to be used in TopDocCollector. I have to admit I don't know how
much
of a benefit this will be in the "typical" case. But I do know
that
there's no such thing as a "typical" case...
I can easily think of a quite typical "worst case" though:
Consider a
collection indexed in order of document age (a pretty typical
scenario
for a long-running index), and then you do a sorting query
(TopFieldDocCollector), asking it to bring the 10 newest
documents.
In that case, each and every document will have a new DocScore
created -
which is the worst-case that Shai feared.
It would be nice if Shai or someone else could provide a
measurement in
that case.
P.S. When looking now at PriorityQueue's code, I found two tiny
performance improvements that could be easily made to it - I
wonder if
there's any reason not to do them:
1. Insert can use heap[1] directly instead of calling top().
After all,
this is done in an if() that already ensures that size>0.
2. Regardless, top() could return heap[1] always, without any if
(). After
all, the heap array is initialized to all nulls, so when
size==0,
heap[1]
is null anyway.
PriorityQueue change (added insertWithOverflow method)
-------------------------------------------------------------------
--
--------------
/**
* insertWithOverflow() is similar to insert(), except its
return
value:
it
* returns the object (if any) that was dropped off the heap
because
it
was
* full. This can be the given parameter (in case it is
smaller than
the
* full heap's minimum, and couldn't be added) or another
object
that
was
* previously the smallest value in the heap and now has been
replaced
by a
* larger one.
*/
public Object insertWithOverflow(Object element) {
if (size < maxSize) {
put(element);
return null;
} else if (size > 0 && !lessThan(element, top())) {
Object ret = heap[1];
heap[1] = element;
adjustTop();
return ret;
} else {
return element;
}
}
[Very similar to insert(), only it returns the object that was
kicked
out of
the Queue, or null]
--
Nadav Har'El | Tuesday, Dec 11 2007,
3 Tevet
5768
IBM Haifa Research Lab
|-----------------------------------------
|A professor is one who talks in
someone
http://nadav.harel.org.il |else's sleep.
-------------------------------------------------------------------
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
