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

Re: XML-appropriate editing data structures

• To: xml-dev@l...
• Subject: Re: XML-appropriate editing data structures
• From: "Thomas B. Passin" <tpassin@c...>
• Date: Wed, 07 Apr 2004 22:56:23 -0400
• In-reply-to: <4074B416.1030807@o...>
• References: <000601c41cf4$0e7fa1e0$6800a8c0@bagpeddlerjlake> <407491E5.4080101@w...> <4074B416.1030807@o...>
• User-agent: Mozilla Thunderbird 0.5 (Windows/20040207)

Bob Foster wrote:

> Recent criticisms of some Eclipse-based XML editors (including mine) (in 
> part) because they use a lot of memory relative to file size underline 
> the fairly obvious fact that XML files are often much larger than 
> programming language files. When the techniques used successfully for 
> programming languages are applied to XML, they can break down.
> 
> The first person I ever saw address this issue directly was Bryan Ford, 
> in his packrat parsing paper 
> (http://www.brynosaurus.com/pub/lang/packrat-icfp02.pdf). Packrat 
> parsing requires an O(n), where n is the document size, data structure 
> with a rather large constant factor. Ford observes "For example, for 
> parsing XML streams, which have a fairly simple structure but often 
> encode large amounts of relatively flat, machine-generated data, the 
> power and flexibility of packrat parsing is not needed and its storage 
> cost would not be justified."
> 

This has reminded me of the Judy array, which can function as a list or 
a dictionary, and is supposed to have very good performance and low 
memory load whether sparsely or densely populated.  This is achieved by 
havin a lrage nuber of specialized substructure types, put into play 
depending on the local data characteristics.  Quoting from an 
introduction to Judy arrays -

"Judy adapts efficiently to a wide range of populations and data set 
densities. Since the Judy data structure is a tree of trees, each 
sub-tree is a static expanse that is optimized to match the "character" 
or density of the keys it contains. To support this flexibility, in 
32[64]-bit Judy there are approximately 25[85] major data structures and 
a similar number of minor structures."

Perhaps a really top XML editor needs a similarly large number of 
specialized tree structures (glad it's not me writing them!).

Cheers,

Tom P

• Follow-Ups:
  • Re: XML-appropriate editing data structures
    • From: Bob Foster <bob@o...>

• References:
  • Converting xml to csv with xslt
    • From: "Jerry Lake" <jerry@b...>
  • Re: Converting xml to csv with xslt
    • From: Mike Fitzgerald <mikefz@w...>
  • XML-appropriate editing data structures
    • From: Bob Foster <bob@o...>

• Prev by Date: RE: XML Schema Question: specifying restrictions for a list of elements
• Next by Date: Re: XQuery question - feel free to ignore
• Previous by thread: XML-appropriate editing data structures
• Next by thread: Re: XML-appropriate editing data structures
• Index(es):
  • Date
  • Thread