Re: "PriorityMap"
- From: Eric Sosman <esosman@xxxxxxxxxxxxxxxxxxxx>
- Date: Sun, 30 Mar 2008 17:28:16 -0400
Andreas Leitgeb wrote:
I'm in search of a data structure for the followig usecase:
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. (whichever is easier to achieve)
The keys (k) are not necessarily unique, in fact I usually get a
couple of different values (v) for each k, and I'm interested only
in the v's, that came with those ten(*) smallest k's. The actual
k's do not matter afterwards.
There are much too many to save them all and filter afterwards.
PriorityQueue and TreeMap do not seem to make it easy to efficiently prune them beyond the first ten(*) entries after each add().
Since it's called in a long loop, efficiency is an issue, but the algorithm itself is also non-trivial, so I can afford some
extra cpu-cycles.
(*): I'd prefer if the "ten" does not need to be hardwired.
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.
--
Eric Sosman
esosman@xxxxxxxxxxxxxxxxxxxx
.
- Follow-Ups:
- Re: "PriorityMap"
- From: Logan Shaw
- Re: "PriorityMap"
- From: Daniel Pitts
- Re: "PriorityMap"
- References:
- "PriorityMap"
- From: Andreas Leitgeb
- "PriorityMap"
- Prev by Date: Re: setting up CLASS PATH dynamically
- Next by Date: Re: setting up CLASS PATH dynamically
- Previous by thread: Re: "PriorityMap"
- Next by thread: Re: "PriorityMap"
- Index(es):
Relevant Pages
|
