Subject: RE: Interesting Side-Effects Problem & Solution From: Avi Kivity <Avi@xxxxxxxxxxxxx> Date: Tue, 15 Dec 1998 10:53:41 +0200 |
On Tuesday, December 15, 1998 05:55, Chris Maden [SMTP:crism@xxxxxxxxxxx] wrote: > Interesting. I prefer another approach for this particular problem. > The list of <page>s is generated within each construction rule, and > then iterated over until one is found whose (all-element-number) is > greater than the current node. It's probably heavier on the The question is, how much heavier? Say that a document contains N nodes, P <page>s, and R locations where <page> references are required. Values for N, P, and R are (say) 3,000,000, 1,000, and 10,000. In Jade, O(N) node accesses are required to build the grove and iterate over <pages>. This is done R times, so the expected running time is O(N*R) = 3*10**10 node accesses. If a better implementation of (tree-before?) and (subtree) is assumed, then this drops to O(N+R*P) = 10**7 node accesses. This might be acceptable, but is quadratic in the size of the document (assuming a constant page size). The linear implementation is O(N), however it requires a separate pass (see below). A sufficiently aggressive DSSSL engine might achieve O(R) operation using something like (process-node-list (ipreced nd)) -- that is, defining the operation recursively -- if caching of procedure calls is provided. But it would probably take more than O(N**R**P) to actually implement this. Does anyone know what it would take to achieve this using the transformation language, assuming only "natural" use? > processor, but it means that you can process arbitrary nodes and get > the right results. For example, in your case, determining the page of > a cross-reference destination would probably be difficult. > Indeed, determining the page of a cross-reference is the only reason for doing this at all! The processing described is a pre-pass, which adds PAGEID attributes to all <page>s, and PAGEIDREF attributes to all referenceable nodes. It becomes a simple matter of double referencing to get to the <page> element associated with a cross-reference. I am not happy with my solution; too often pre-processing passes have to be invoked on the data, which is exactly the opposite of what my conception of how dsssl processing should be like -- a sequence of transformations, followed by a rendering, but performed in parallel (composed) rather than sequentially (passes). DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: Interesting Side-Effects Proble, Avi Kivity | Thread | Re: Interesting Side-Effects Proble, Chris Maden |
Using attribute values, Linda van den Brink | Date | Sorting (was Re: How do I do this i, kubek |
Month |