RE: Interesting Side-Effects Problem & Solution

[Avi Kivity <Avi@xxxxxxxxxxxxx>]

On Tuesday, December 15, 1998 18:14, Chris Maden [SMTP:crism@xxxxxxxxxxx]
wrote:
> [Avi Kivity]
> > The question is, how much heavier?
> > 
> > Say that a document contains N nodes, P <page>s, and R locations
> > where <page> references are required.
> 
> My implementation only refers to P at R, so I think the weight is
> PR.
> In total, the number of node references would be N+PR; each node is
> processed once, and in addition, the pages are processed for each
> reference.
> 

Let's see (assuming current Jade implementation):

(select-elements (subtree (current-root)) 'page) - O(N)
(node-list-filter (all-element-number-above something) (...)) - O(P)
(element ref (...)) - O(R)

In total - O((N+P)*R) = O(N*R)

A little more efficiency can be squeezed out by a variant of
(subtree) which ignores non-element nodes.

Of course, an implementation which imlements the first operation 
in O(P) (which is feasable, though not immediate) would
achieve O(P*R) operation.

- Avi
---------------------
"Thou shalt not travel faster than light" - Carl Sagan, Contact



 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist