Subject: Re: Better/Faster method to find the next element in tree order with certain GIs From: "P. Stritzi" <e6g1m6n3@xxxxxx> Date: Wed, 5 May 1999 00:04:16 +0200 (MEST) |
Hi, I'm partially answering my own question: > I need to find the next element in tree order that > has a GI that is in a specified set. I need this > when producing a set of HTML pages from a single XML > file to build a [Next] Link. > The code I came up with is not quite fast (it takes > about 2/3 of the overall running time) and I have the > feeling there should be a more elegant solution. This was a not correctly observed, I did Benchmarks and it was much worse it took over 90% of the runtime for preparing HTML pages (with -t sgml BTW) and that with only one call per page. > One alternative I can think of is to look at the > elements in tree order by looking at the children > first then recurse for the next sibling, if its the > last to the siblings of the parent etc. until I find > the wanted element. But this doesnt sound very > elegant to me even it may be faster for my data. This approach speeded the code from a runtime of 11min20sec to 2sec!! The question remaining is: Is there a simpler variant thats at least not slower? If not I would write the code for the inverse function and both could be added "Procedures Library" Peer Stritzinger ------------------------------------------------------------ ;My current implementation looks like this: ; This is only a helper function for find-tree-first (define (find-nodelist-descend xnl predicate?) (let ((nl (select-by-class xnl 'element))) (if (node-list-empty? nl) #f (let ((fnl (node-list-first nl))) (if (predicate? fnl) fnl (or (find-nodelist-descend (children fnl) predicate?) (find-nodelist-descend (node-list-rest nl) predicate?))))))) ; Finds the first element after SNL in tree order for which ; PREDICATE? returns true. Returns a singleton node list or ; #f if not found. (define (find-tree-first snl predicate?) (or (find-nodelist-descend (children snl) predicate?) (find-nodelist-descend (follow snl) predicate?) (let loop ((par (parent snl))) (if (node-list-empty? par) #f (or (find-nodelist-descend (follow par) predicate?) (loop (parent par))))) (empty-node-list))) ; Example for find-tree-first usage (define pageoids '("page" "pro-data" "pro-group" "product" "pro-multi" "ib-entry")) (define (pageoid? snl) (if (member (gi snl) pageoids) #t #f)) (define (next-pageoid snl) (find-tree-first snl pageoid?)) --- Sent through Global Message Exchange - http://www.gmx.net DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Better/Faster method to find the ne, P. Stritzi | Thread | the Link object and the tex backend, Didier PH Martin |
Re: About the source library, Sebastian Rahtz | Date | JADE-DEV: ANNOUNCE: Jade Source Con, Avi Kivity |
Month |