Re: sorting with xml and friends

(Neil Zanella) writes:

> Hi Martin,
>
> Your answer was very interesting. It seems like extensible sytlesheet
> transformations can prove extremely useful these days. However I would
> like to inquire about the actual time complexity of the algorithm
> described by the XSLT code you posted. Is this implementation
> detail that is transparent to the XSLT programmer?

In a word: yes.

XSLT is (nearly) a functional programming language, relying heavily on
recursion for all but the simplest operations. This fact actually has
pretty much nothing to do with the code in this specific example, but
it's enough to realize that efficiency simply wasn't one of the design
goals of XSLT. It is still a fairly elegant language to work with, and
I kind of like to use it to excercise my programming skills in a
non-procedural language; gets you thinking in different ways.

I would guess that many XSLT implementations utilize intelligent
sorting algorithms, but it really doesn't matter all that much, since
the language itself lends itself toward inefficiency.

OTOH, it doesn't seem unreasonable that one could write software which
would compile XSLT into an optimized procedural equivalent, perhaps
even noting what nodes might do well to be indexed specially for
maximum efficiency. A sophisticated engine could probably rewrite code
to produce the same behavior, but with much better efficiency than the
most straightforward approach.

-Micah

Micah Cowan