W3C home > Mailing lists > Public > www-dom@w3.org > October to December 1998

RE: An observation about "live" NodeLists

From: Miles Sabin <msabin@cromwellmedia.co.uk>
Date: Mon, 19 Oct 1998 10:01:03 +0100
Message-ID: <c=US%a=_%p=Cromwell_Media%l=ODIN-981019090103Z-23467@odin.cromwellmedia.co.uk>
To: "'Mark Robinson'" <markr@sites-online.com>, "'Stephen R. Savitzky'" <steve@crc.ricoh.com>
Cc: "'www-dom@w3.org'" <www-dom@w3.org>
Mark Robinson wrote,
> or just not deal with the indexing at all, like:
>       Node n = nl.item(0);
>       while( n != null )
>       {  n.getParentNode().removeChild(n);
>          n = nl.item(0);
>       }
> Right?

I nearly posted this solution along with my explanation
of the problem, but I had second thoughts ...

Unfortunately code like this might well perform *very*
badly for some implementations. The problem is likely
to be that the removal of the first NodeList item will
invalidate *all* of any associated cache. The likely
consequence of that is that each nl.item(0) will force
a search starting with the first descendent of the root
node of the NodeList.

It's a bit early on Monday morning, but I reckon that
in those circumstances the complexity of this algorithm
will be something like O(n^2) where n is the number of
descendents of the root node of the NodeList.

I'd like to be able to say that the 'remove from the
greatest index downwards' solution is likely to be better,
but unfortuantely that's potentially implementation
dependent too. It'll be O(n) for my implementation, and
probably many others, but, in general, who knows?

I think this highlights another, slightly subtler, set
of portablility issues. Because of the way the DOM
interfaces have been specified, there's no 'natural'
implementation. Consequently any implementation is
likely to be a horrible compromise, supporting some
operations with acceptable performance, and others with
not so acceptable performance. The effect of this is
that in many cases DOM users will have to tune their
code to different implementations ... which is almost
as bad as being forced to code to different interfaces.

By way of contrast, consider the Standard C++ library.
Here a great deal of effort was made to give standard
complexity requirements, as well as standard interfaces,
with two results: library implementors are pretty much
forced to implement in similar ways; but users can rely
on behaviour. I think that was a good choice: speaking
as someone who's implemented the C++ libs, I can vouch
for the fact that this can make life awkward for
implementors, but as a library user, I'm extremely glad
that the std allows me to assume list::sort() has
O(n log n) complexity.



Miles Sabin                          Cromwell Media
Internet Systems Architect           5/6 Glenthorne Mews
+44 (0)181 410 2230                  London, W6 0LJ
msabin@cromwellmedia.co.uk           England
Received on Monday, 19 October 1998 05:06:37 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 20 October 2015 10:46:05 UTC