RE: Interesting Side-Effects Problem & Solution

Subject: RE: Interesting Side-Effects Problem & Solution
From: Avi Kivity <Avi@xxxxxxxxxxxxx>
Date: Tue, 15 Dec 1998 23:41:10 +0200
On Tuesday, December 15, 1998 18:14, Chris Maden [SMTP:crism@xxxxxxxxxxx]
> [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:

Current Thread