[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: DOM Impl: Array or Linked List?
Docuverse DOM SDK is implemented using the array approach with the last accessed index cached to improve next/prevSibling performance. Resulting implementation is fast for index-based access to child nodes and slightly slower for sibling-based access (only 10% slower than linked-list version). Modification to the tree is fast when appending nodes (i.e. building new tree) but is somewhat slow when inserting new nodes since array contents have to be shifted around. If your XML document has gazillion child nodes per element, performance will suffer quite a bit. You can get around the update problem by applying the Strategy pattern to child array implementation. On insert, check to see if the array is big enough to justify using different type of array implementation (i.e. sparse array). One caveat is that this tends to increase the number of child list array (smart NodeLists and NodeList implementation strategies). There are ways to minimize this problem though. So the bottom line is, you are on the right track. Don Park Docuverse -----Original Message----- From: Clark Evans <clark.evans@m...> To: xml-dev@i... <xml-dev@i...> Date: Wednesday, March 10, 1999 4:15 PM Subject: DOM Impl: Array or Linked List? >I've been struggling with this slightly, and would >like your feedback. I'm building a DOM tree. For >the internal representation, I see two options: > >A) A linked list for children > >* Easy inserts in middle of list >* Slower non-sequential reads > >B) An array for children > >* Harder inserts in middle of list >* Faster non-sequential reads > >Anyway, I was thinking of implementing >a compromise, a sparse array with >configurable spacing, depending upon >the document. > >Thoughts? > >Thank you. > >Clark > >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/ and on CD-ROM/ISBN 981-02-3594-1 >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...) > > 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/ and on CD-ROM/ISBN 981-02-3594-1 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...)
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|