On 03/12/13 12:17, jean-marc Mercier wrote:
> You can create a simple linked list using a cons cell:
@John : Right, but you will always have quadratic complexity in length
creating the sequence $seq.
Not always. But that was just example code - don't create it from a
sequence.
>I can only speculate, because we haven’t seen your implementation, but
I am wondering why you didn’t take advantage of John’s existing>
$lessthan function argument in order to compare all kinds of items?
@ Christian. Indeed, I realized after profiling my rewriting of John
code that its code implementation has also a quadratic complexity in
sequence length. John, as I, need at a point to allocate memory for
writing this tree implementation. If we want to stay pure xquery, this
will be done with quadratic complexity in length, at least I can't see
any work around to that.
My red/black tree implementation only ever uses sequences of length 4,
which will therefore have a constant cost to create (in the size of the
red/black tree).
John
--
John Snelson, Lead Engineer http://twitter.com/jpcs
MarkLogic Corporation http://www.marklogic.com
_______________________________________________
[email protected]
http://x-query.com/mailman/listinfo/talk
