I'm not sure about that. TreeMaps are pretty lightweight -- they
only allocate an Entry (cons cell, effectively) for each entry in the
map. In-order traversals are O(n); lookups are O(lgn) (probably
\Theta(lgn)), but lookups are the degenerate case.
I actually just did a little performance comparison -- Trees vs
Hashes, and for anything smaller than 10-15 entries, the comparative
cost of lookup is negligible, and the memory footprint is smaller
with sortable collections. Anyone want the test code? Just ask.
-Fred
On Mar 21, 2007, at 4:29 PM, Daniel Kulp wrote:
On Wednesday 21 March 2007 15:42, Fred Dushin wrote:
Someone else mentioned that it might be nice to have he notion of an
interceptor id, which I'd fully agree with, so that you could do a
lookup by id. Your interceptor lists are then just (sortable) maps
(or multimaps, as the case may be), and lookup can be done in O(lg
n). But that's a pretty disruptive change to the whole
architecture. OTOH, better to do it now than once the cat is out of
the bag...
It also has nasty performance impacts as the traversals would be much
more expensive. Since those traversals happen on EVERY SINGLE
message,
that would be really bad. Also, maps use significantly more memory
than the ArrayLists do.
My only real thought on this would be to change from List to Set
and use
the CopyOnWriteArraySet. That keeps the performance of the ArrayList
for the traversals. It also gives you the guarantee of uniqueness in
the Set. (providing you write an appropriate .equals(...) method)
The main cost is more expensive "add", "remove", and "contains"
methods.
However, that should be a startup cost in 95% of the cases.
Anyway, it's a thought.
--
J. Daniel Kulp
Principal Engineer
IONA
P: 781-902-8727 C: 508-380-7194
[EMAIL PROTECTED]
http://www.dankulp.com/blog
