John, I did the test again for rbtree.xq. The results are below : n is the number of insertion in your map, time is the the time in ms taken to insert these n entries. Your tree is showing a n log(n) complexity. Probably as mine, since I kept the same basic data structures.
Well..I am confused. At this point, I should apologize, my first measure was not correct. Thanks for your patience. n time ms 10000 1094.53 20000 2091 40000 4089.92 80000 8422.22 160000 18044.36 320000 37290.56 640000 77491.2 2013/12/3 John Snelson <[email protected]> > 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
