All good points. I hadn't considered the need to set the order, only
that there is *an* order.
Again, wallowing in my own ignorance :)
-Fred
On Mar 21, 2007, at 5:13 PM, Daniel Kulp wrote:
Fred,
On Wednesday 21 March 2007 17:05, Fred Dushin wrote:
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.
I'm more concerned with the cost of the iterators of the "Thread Safe"
variants of the various types: (the value set iterator on the maps)
CopyOnWriteArrayList
CopyOnWriteArraySet
ConcurrentHashMap
Collections.syncronizedMap(new TreeMap())
Technically, I'd also argue that the TreeMap and HashMaps are NOT
appropriate. The Lists provide and order of how the stuff are added
into the chain. Thus, the only map that would really meet that is:
Collections.syncronizedMap(new LinkedHashMap())
Dan
-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
--
J. Daniel Kulp
Principal Engineer
IONA
P: 781-902-8727 C: 508-380-7194
[EMAIL PROTECTED]
http://www.dankulp.com/blog
