Christian,Hi>thanks a lot for your profiling results and the attached XQuery modules
Since I am currently extensively using these files, I spotted and corrected some bugs. I will provide a more robust code as soon as I consider them as stables.Notice that I am also using sets to have a meaningful except, intersection or union operators for nodes or functions. Indeed, the definition given in http://www.w3.org/TR/xpath-functions/#union-intersection-except is not very clear for me.Jean-Marc
2013/12/7 Christian Grün <christian.gruen@gmail.com>
Hi Jean-Marc,thanks a lot for your profiling results and the attached XQuery modules, very appreciated. Your code may serve as good inspiration for other users getting into the world of higher order functions. We’ll consider your input once we make existing modules public in a central repository (sth. that has been planned for a while, but... well, is one of many other projects we are working on).Christian___________________________On Fri, Dec 6, 2013 at 4:29 PM, jean-marc Mercier <jeanmarc.mercier@gmail.com> wrote:
Christian,Hi.To end this topic, you should find enclosed two files that fulfills now my requirements. I found these objects very practical, their purpose are to handle set or maps of nodes / functions.I am publishing them here very informally, hoping other BaseX users could find them as helpful as I do, or maybe yourself, or a standardization committee.- The first one, idmap.xqm, allows to use maps, with nodes or functions as keys.
- The second one, set.xqm, allows to define set of items (I use such an object to define a stack).These files consists in small overload of the BaseX map module. Both require an external id function of atomic type, that must be provided by the user.Below are the profile tests for these maps and set. The profile function is located into idmap:profile($i,$j) to be run by others. Basically, the "idmap" seems to be five time slower than BaseX map for inserting atomic types. Set seems to be quite comparable to BaseX map. This overload come from perf issues in XQUERY, but I can handle this small overload for my purposes. Obviously, for atomic type, it is better to use directly the map module, and these objects embed a basic protection to avoid a misusing.Some remarks :1) It means that users are linked to BaseX map module when they are using these objects. As you already know, I tried unsuccessfully to write them in pure XQUERY, one of the motivation was not to be linked an external module.
2) Using a map module to define a set is not really the best way to proceed, but it seems that XQUERY 3.0 users don't have any other choice.3) I think that BaseX could provide a simplified access to such objects. Indeed, the BaseX interpreter must have a default id for nodes or functions that it could expose to users, or use it directly through the BaseX map module.Hope that helpsCheers,Jean-Marc
Tag name/Text nb integer_set node_set integer_map Basex_integer_map node_map test 1024 24.63 ms 43.36 ms 51.6 ms 6.35 ms 70.92 ms test 2048 10.91 ms 46.71 ms 17.52 ms 3.57 ms 51.62 ms test 4096 1.71 ms 31.52 ms 11.7 ms 1.04 ms 23.59 ms test 8192 2.49 ms 22.88 ms 15.41 ms 1.72 ms 32.5 ms test 16384 5.12 ms 20.23 ms 33.47 ms 2.9 ms 50.62 ms test 32768 8.31 ms 31.54 ms 58.95 ms 5.77 ms 86.86 ms test 65536 20.1 ms 71.39 ms 99.57 ms 13.0 ms 162.09 ms test 131072 48.15 ms 157.27 ms 680.47 ms 33.68 ms 947.9 ms test 262144 99.67 ms 305.88 ms 1132.31 ms 77.85 ms 683.37 ms test 524288 239.43 ms 569.46 ms 1769.53 ms 383.77 ms 2903.24 ms test 1.05E+06 737.79 ms 2485.75 ms 5022.02 ms 1031.71 ms 10204.07 ms 2013/12/1 jean-marc Mercier <jeanmarc.mercier@gmail.com>
Christian,Concerning this topic, it took me a whole week of quite hard work to write a Red / Black removable tree written in XQUERY, together with a map interface that mimic the basex one. However I won't go public, and would advise not to use it, because it suffers from performance issues.I opened a thread concerning this perf issue, that might be deeper that I thought.Cheers,Jean-Marc2013/11/21 Christian Grün <christian.gruen@gmail.com>>>Sounds interesting. Have you thought about making it public to getThat would be fast anyway… I’m looking forward to the result!
>> more feedback?
> I will, as soon as it will be tested... I need to implement a
> remove($map,$key) function, meaning that I have to re-implement the whole
> BRTree...This will take some time (2 days works I guess to have a clean
> implementation), to find into my agenda :)
Christian
>>It’s an implementation of Phil Bagwell’s immutable hash tries (as
>>mentioned in your previous thread…):
> Oops..sorry, my linker is slow sometime ;) Thanks for your patience
>
>
> 2013/11/21 Christian Grün <christian.gruen@gmail.com>
>>
>> > 1) I implemented in pure XQUERY 3.0 a map having the desired behavior. I
>> > can
>> > now define optionally an ordering function, and thus is able to insert
>> > nodes, maps, sequences. It is very useful for a lot of things. I would
>> > not
>> > recommend to external person to use it at present time (not tested,
>> > functionalities to add, bugs suspected), but I can provide the file on
>> > demand.
>>
>> Sounds interesting. Have you thought about making it public to get
>> more feedback?
>>
>> > 2) A question about the BaseX map module : what kind of tree technology
>> > is
>> > used behind ?
>>
>> It’s an implementation of Phil Bagwell’s immutable hash tries (as
>> mentioned in your previous thread…):
>>
>>
>> https://github.com/BaseXdb/basex/tree/master/basex-core/src/main/java/org/basex/query/value/map
>>
>> Christian
>
>