[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: Computational complexity of accessing the Nth item
> If there is more than one reference to $sequence, or if the reference is in > a loop, then the value of $sequence is calculated progressively: any > reference to $sequence[$N] ensures that at least $N items of $sequence have > been evaluated, and then returns the $N'th item by calling Java's > ArrayList.get($N-1), which I believe executes in constant time. > So, if I have understood correctly, having $sequence[last()] (and somehow more than one reference to $sequence) will guarantee that any further access to the items of $sequence will be performed in constant time? Cant this be pre-computed automatically by the XSLT processor? Something like computing a function with @memo-function="yes", but done by the XSLT processor? Cheers, Dimitre. On Mon, 3 Jan 2005 12:33:20 -0000, Michael Kay <mike@xxxxxxxxxxxx> wrote: > > > > I wonder what should be the most likely computational complexity of: > > > > $sequence[$N] > > Highly dependent on the circumstances. > > Let's assume $N is known statically to be an integer. > > Let's assume Saxon 8.2. > > If there is only one reference to $sequence, and it isn't in a loop, then > the expression from which $sequence is calculated is effectively inlined; > this expression is then evaluated iteratively, and execution is terminated > when the N'th item is reached. > > If there is more than one reference to $sequence, or if the reference is in > a loop, then the value of $sequence is calculated progressively: any > reference to $sequence[$N] ensures that at least $N items of $sequence have > been evaluated, and then returns the $N'th item by calling Java's > ArrayList.get($N-1), which I believe executes in constant time. > > > Another question is whether the functions on sequences are faster that > > manipulating them "by hand". > > I think the answer is likely to be: sometimes yes, sometimes no. Sometimes > Saxon may be able to exploit knowledge that's not available to the user, > sometimes the user may be able to exploit knowledge that's not available to > Saxon. > > > > > One translation in more practical terms: would it be realistic to try > > to perform binary search in a sorted sequence? > > Yes, I think that's a reasonable thing to attempt. > > Michael Kay > http://www.saxonica.com/
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|