Re: Better/Faster method to find the next element in tree order with certain GIs

["P. Stritzi" <e6g1m6n3@xxxxxx>]

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