[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Walking the DOM (was: XML APIs)

• From: Tim Bray <tbray@t...>
• To: John Cowan <cowan@l...>, XML Dev <xml-dev@i...>
• 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@i...
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@i... the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@i... the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@i...)

• Follow-Ups:
  • Re: Walking the DOM (was: XML APIs)
    • From: Paul Prescod <papresco@t...>
  • Re: Walking the DOM (was: XML APIs)
    • From: John Cowan <cowan@l...>
  • Re: Walking the DOM (was: XML APIs)
    • From: Dan Rabin <drabin@A...>

• Prev by Date: Apologies for misdirected mail
• Next by Date: Re: CDATA by any other name... (was The raw and the cooked)
• Previous by thread: Walking the DOM (was: XML APIs)
• Next by thread: Re: Walking the DOM (was: XML APIs)
• Index(es):
  • Date
  • Thread