Re: "PriorityMap"

Eric Sosman wrote:
Andreas Leitgeb wrote:

Some algorithm spits out *lots* of pairs (k,v) of type (int,long).
I only want either those ten(*) pairs with the lowest keys, or all
pairs with the lowest ten(*) keys.

Since you have "*lots*" of (k,v) pairs, it would probably
be nice to avoid the overhead of creating an Integer and a Long
and a Map.Entry (or similar) for each pair. I'd suggest just
coding the thing up for the purpose at hand -- a simple heap
made out of an int[] and a long[] seems attractive. Should be
pretty fast, too: Once you've been through a few thousand pairs,
most of the remaining pairs will be bigger than the heap's root
and will be rejected on the first comparison.

Yeah, assuming you don't have the bad luck of somehow occasionally
getting all the pairs in decreasing order.

Another approach is just ditch the heap and do linear search. In
other words, keep track of the largest int value in the int[] array,
and if you find one smaller, go find the one to evict using brute
force linear search. Since this will happen so infrequently, and
since 10 is very small in comparison to millions, this should be
pretty negligible. An advantage of this approach is that it's easy
to make it "stable", which I'm defining as this: if two values of
equal value arrive but they both can't fit in the output of ten
pairs, you keep the first one you saw.

Also, you could use a heap, but optimize the common case by duplicating
the value at the top of the heap as a separate variable of type int.
Then you get the full generality and good asymptotic performance,
but 99.9% of the time when you are comparing to the top of the heap,
you avoid creating an Integer object.

- Logan
.

Relevant Pages

  • would yo please provide help?
    ... i have written a code of a 'MINIMUM' Heap the code seems ... private int maxSize; ... int largerChild; ... String sel; ...
    (comp.lang.java.programmer)
  • Re: smail remote and local root holes (really, it is exploitable)
    ... * heap is at 0x080d.. ... ssize_t Send(int s, const void *buf, size_t len, int flags) ...
    (Bugtraq)
  • Heap fragmentation
    ... in University I learnt about heap fragmentation, ... over this procedure I cycle a hundred times. ... int main{ ...
    (comp.realtime)
  • Re: Two questions about C# datatypes
    ... int is value type so it is stored on stack. ... class is reference type ... and it is stored on heap. ... a class containing a struct will create an object where the struct is part of the memory allocated to the object. ...
    (microsoft.public.dotnet.languages.csharp)
  • I have HEAP big trouble
    ... So I was looking at the heap usage with a small ... int CountWalk() ... // extra termination required to avoid infinite loop!!! ...
    (microsoft.public.vc.debugger)