<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Tatu,<br>
<br>
I would be interested in your code... just let me know what kind of
copyright/licensing<br>
you and other parties are upholding.<br>
<br>
At this point I would also thank the list for covering the topic
extensively...<br>
I'll try to summarize shortly.<br>
<br>
Thanks!<br>
Martin<br>
<br>
Tatu Saloranta wrote:
<blockquote cite="mid20050428221923.92017.qmail@web41729.mail.yahoo.com"
type="cite">
<pre wrap="">--- Elias Ross <a class="moz-txt-link-rfc2396E" href="mailto:eross@m-qube.com"><eross@m-qube.com></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap="">On Thu, 2005-04-28 at 13:21 -0700, Tatu Saloranta
wrote:
</pre>
<blockquote type="cite">
<pre wrap="">As to the access time itself, I'm fairly confident
that the HashMap solution is pretty much always
</pre>
</blockquote>
</blockquote>
<pre wrap=""><!---->...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">HashMap which is more heavy-weight than a simple
array/List.
</pre>
</blockquote>
<pre wrap="">It's pretty hard to come up with a solution that
satisfies the
degenerate case (Elements with lots of attributes)
and the common case (one or two attributes.)
</pre>
</blockquote>
<pre wrap=""><!---->
True.
</pre>
<blockquote type="cite">
<pre wrap="">I suggested sorting the attributes and doing a
binary search would be
okay, but it seemed not terribly popular.
</pre>
</blockquote>
<pre wrap=""><!---->
One problem is that unfortunately sorting and binary
searching are
not very inefficient with Java Strings (compared to
HashMap).
This based on comparison I made at one point; the
default\
HashMap implementation (JDK 1.4+) is pretty damn fast,
compared to about any other generic alternative, when
the main goal is fast
access time. If you have a String handy, and
especially if it has been
intern()ed, it is very hard to get anything faster.
Binary search on Strings
would be faster than linear search, but only
significantly so for larger
sets (larger than what HashMap's minimum).
Sorting + binary search would be a decent choice if
one wants to access
attributes in alphabetic (etc) order. Of course you
could also sort by
hash value, which would allow for bit faster access
(and 'random' ordering
when iterating over it), but still not as fast as
hash-based alternative...
</pre>
<blockquote type="cite">
<pre wrap="">One solution would be to add a protected constructor
</pre>
</blockquote>
<pre wrap=""><!---->or factory to
</pre>
<blockquote type="cite">
<pre wrap="">Element that would allow an alternative attribute
list implementation to
be specified. Then, clients could create their own
DOMBuilder which returns Elements with this new
</pre>
</blockquote>
<pre wrap=""><!---->attribute class.
</pre>
<blockquote type="cite">
<pre wrap="">This isn't exactly clean either, but might be good
</pre>
</blockquote>
<pre wrap=""><!---->enough.
And/or the default implementation would choose one
that seems most suitable; at least for documents built
from parser.
In this case it is known how many attributes there
are, although
usage patterns are not known. One could extend JDom to
use simple
"profiles" (read-only trees -> optimize a bit for fast
access don't worry
about mods; heavy modifications -> balance the needs;
read-and-cache -> optimize for long-running
access-have structs, for
long-living objects) that could choose more optimal
structures.
It's not actually all _that_ difficult to create a
specialized List
that has fast by-name access, compact presentation
(doesn't use
more memory than ArrayList with Attribute objects
inside), simple
indexed access, and that's still quick to construct,
given initial
size needed. This because while ArrayList and HashMap
are very good
general-purpose data containers, it's usually possible
to create
even better special-purpose ones for specific need...
and this is
one case where such a "ListMap" could be done.
I have some code available if someone is really
interested in pursuing
this. In its current form its even more highly
specialized (for the
needs of StAX 1.0 XMLStreamReader's attribute access,
and can
count on all names being intern()ed), but it would at
least show
one approach (kind of hybrid flat Map with contiguous
shared spill
area... yeah, I'm sure that pretty much sums it up!
:-) ) that
has performed nicely.
-+ Tatu +-
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
<a class="moz-txt-link-freetext" href="http://mail.yahoo.com">http://mail.yahoo.com</a>
_______________________________________________
To control your jdom-interest membership:
<a class="moz-txt-link-freetext" href="http://www.jdom.org/mailman/options/jdom-interest/youraddr@yourhost.com">http://www.jdom.org/mailman/options/jdom-interest/youraddr@yourhost.com</a>
</pre>
</blockquote>
<br>
</body>
</html>