Hello. To end this thread, I would like to give the results of two different XQUERY implementations of a Red / Black tree for integer insertion.
The first conclusion of this work seems that none of these implementations are actually usable, due to poor performances. The best way to build a map, or a stack, that can handle nodes or functions as keys, should be to encapsulate the existing map modules provided by interpreters with a small xquery code. Indeed, the map module I used is more than 1000 time faster for inserting pairs of integers. A remark : I don't think possible to write a more efficient implementation for Red Black tree insertion than John Snelson one. Mine is about 5 time slower, because I introduced a lot of overload to be able to remove nodes, and of course because I am not as XQUERY experimented as John. Another conclusion might be that it does not seem possible to write extensively computing algorithms with XQUERY. Indeed, I was wondering why these codes are showing so poor performances. Might it be due to the interpreter optimization query process ? Left column (nb) is the number of insertion. removable.xq is the tree that I implemented, rbtree is the original John Snelson one. nbremovable.xqrbtree.xq25.33 ms0.75 ms410.12 ms1.42 ms829.59 ms4.11 ms1660.74 ms7.6 ms3248.97 ms6.18 ms6451.5 ms4.98 ms12848.98 ms10.49 ms25692.06 ms18.73 ms512184.55 ms35.92 ms1024325.48 ms69.97 ms2048661.12 ms136.05 ms40961315.19 ms266.68 ms81922793.02 ms573.12 ms163846053.26 ms1265.82 ms3276812938.48 ms2620.19 ms6553627746.55 ms5655.38 ms13107259775.33 ms12058.8 ms 2013/12/3 jean-marc Mercier <[email protected]> > David, thanks, I feel less miserable :) > > The point is that I want a map (maps are standard in XQUERY) but that can > handle nodes or functions as keys, provided an external ordering function > is given. I also want a stack having the same properties. Such containers > does not exists, thus I decided to write them in pure xquery. My motivation > was to exercise myself, as well as testing whether xquery could fit my > algorithmic needs. I did it, starting with John Snelson work, that kindly > point me out its work over this topic. > > I thought that my code and John Snelson one had not the desired complexity > while profiling my code. I was just wrong. All this conversation took place > because I made bad measurements :( > > > > > > > 2013/12/3 David Lee <[email protected]> > >> Jean-marc, I completely understand your frustration with the lack of >> "standard" data types like double linked lists, maps, stacks etc. >> >> I also had the same problem at first. However in general I have found >> that looking for these types meant I was trying to solve the problem in a >> way >> >> which is not the best way in a functional language, and that there were >> other ways of solving the same problem - often more elegantly. >> >> >> >> So I suggest you describe to the group, at a higher level, what kinds of >> problems you are trying to solve where you feel these data types are >> necessary. >> >> It may be that there are better ways of solving the problem without them. >> >> Or it may be that these types are really needed and things like johns rb >> tree should be suggested as standard or atleast common libraries (such as >> in functx). >> >> >> >> >> >> >> >> ---------------------------------------- >> >> David A. Lee >> >> [email protected] >> >> http://www.xmlsh.org >> >> >> > >
_______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
