OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: Walking the DOM (was: XML APIs)

[ Lists Home | Date Index | Thread Index ]
  • From: Tim Bray <tbray@textuality.com>
  • To: John Cowan <cowan@locke.ccil.org>, XML Dev <xml-dev@ic.ac.uk>
  • Date: Tue, 03 Nov 1998 10:27:31 -0800

At 12:50 PM 11/3/98 -0500, John Cowan wrote:
>Stephen R. Savitzky wrote:
>> [T]he classic algorithm for traversing a tree is:
>> traverse(node) {
>> }
>The trouble with that algorithm is that it is recursive.  It will
>blow up if the tree is sufficiently deep.  Indeed, in
>languages that cannot be relied on to do tail recursion, like
>Java, it will blow up if the tree is merely sufficiently wide.

Wouldn't the effects of recursion will be lost in the static,
compared to the effects of loading the doc into memory to facilitate
tree processing?  Even if you are doing some persistent-ancillary-
info trick to do a virtual tree, in my experience for very large
docs you really have to wrangle memory carefully.  It seems
really counter-intuitive that the stack & local variables overhead
caused by recursion is going to get you before one of these
other things.   Unless of course you recurse in some huge
sloppy badly-written routine with lots of local junk.

BTW, what languages can be relied on to do tail recursion?

Also, shorter algorithms are better. -Tim

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@ic.ac.uk)


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS