Re: [gdome]Question about efficiency of gdome_el_getElementsByTagName, et al.

[Luca Padovani <lpadovan cs unibo it>]

Hi,

On Mon, 2004-01-05 at 00:32, Robby Dermody wrote:
> Quick question. As GDOME is based on a tree model, I would guess that the
> efficiency of gdome_el_getElementsByTagName() at finding and retrieving an
> element out of a certain level of the tree is O(log n) or a derivative of
> log thereof, as opposed to O(n)?

Quick answer: it is O(n^2)!!!!! :-((((((((((((((

> Basically, I'm asking this because say the tree has 100,000 entries, and you
> want to look for one with the name "Foo232", which happens to be the last in
> this list. I think we'd all want that to be at O(log n) time :)

for sure we'd all want efficient traversal, alas NodeList is the wrong 
object to play with (along with NamedNodeItems). The point is that DOM 
requires these structures to be live, which means, say I'm in the middle
of a traversal and the document gets changed for whatever reason, then 
the NodeList I'm iterating on must reflect the changes. Gdome is 
conservative: whenever you ask for item(i) on a NodeList it starts 
scanning the nodes from the "beginning" (which, depending on how you 
obtained the NodeList, may be the document root or another node), 
leading to quadratic traversal time.

In principle (read: not implemented) there is a possible optimization,
which is to give NodeList a state, the last node visited, and to use the
event notification meachanism to invalidate the state when a change occurs.
The optimization works on the assumption that the next node visited will
very likely be close to the previous one.
In this case a traversal of the whole document with no modifications
occurring meanwhile would be linear in the number of nodes.

I'm not sure this is worth the trouble, though (there are some subtleties),
and in fact in those few cases when I needed such sort of functionality I
just implemented my own iterator.

Cheers,
-- luca