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