Re: [xsl] Computational complexity of accessing the Nth item in a sequence and in a node-set

[Dimtre Novatchev <dnovatchev@xxxxxxxxx>]

> 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/