Hello,
The following query
map:size(map:new(({<dummy>dummy</dummy>:""},{<doudou>dummy</doudou>:""})))
returns ..1.
Does it means that the map module uses the function fn:data() to compute keys for nodes ??
Cheers
Jean-Marc
Hi Jean-Marc,
The following query map:size(map:new(({<dummy>dummy</dummy>:""},{<doudou>dummy</doudou>:""}))) returns ..1.
Does it means that the map module uses the function fn:data() to compute keys for nodes ??
Pretty much like that: The rules of the distinct-values() function are used to decide if two keys are equal. See [1] for more details.
Christian
[1] http://docs.basex.org/wiki/Map_Module#map:new
Cheers
Jean-Marc
BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk
Hi Christian
You are right, the behavior from the link http://docs.basex.org/wiki/Map_Module#map:new is pretty clear.
Two remarks :
- might this mechanism not be a little bit misleading ? Indeed, I was expecting somehow that map:key(map:new({<node>:""})) to be an identity for <node>. Moreover, maps using elements as keys are of great interest. Could it be a suggestion to provide an optional binding to the key / value mechanism to tune the behavior of the map module ?
- A remark of minor importance : if distinct-values() is used to select keys, the map:module shouldn't accept sequences as keys ? If I try a map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.
2013/11/18 Christian Grün christian.gruen@gmail.com
Hi Jean-Marc,
The following query
map:size(map:new(({<dummy>dummy</dummy>:""},{<doudou>dummy</doudou>:""})))
returns ..1.
Does it means that the map module uses the function fn:data() to compute keys for nodes ??
Pretty much like that: The rules of the distinct-values() function are used to decide if two keys are equal. See [1] for more details.
Christian
[1] http://docs.basex.org/wiki/Map_Module#map:new
Cheers
Jean-Marc
BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk
- might this mechanism not be a little bit misleading ? Indeed, I was
expecting somehow that map:key(map:new({<node>:""})) to be an identity for <node>.
You’ve got me stumped here. The talk@xquery.com mailing list may be the best place to get more details on this.
- A remark of minor importance : if distinct-values() is used to select
keys, the map:module shouldn't accept sequences as keys ? If I try a map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.
I guess you answered your own question? ;)
All the best, Christian
You’ve got me stumped here. The talk@xquery.com mailing list may be the best place to get more details on this.
I will try to post to this mailing list, thanks for the link. Indeed I started to implement through xquery a map version able to handle nodes for my needs. It is not obvious, because a map requires to define an equality properties over set. For nodes, deep-equal is a natural candidate, but it does not define an ordering, and performances are lost. For database nodes, it is possible to achieve this with internal (or maybe pre-database) ids, but I can't use it for dynamically created nodes. I guess that the best choice is to provide an optional binding to an external ordering function, something like *map:new**($maps as map(*)*, binding as map(*)) as map(*)*, where the binding provides an option to the ordering function (e.g. $order(key1,key2) := binding["order"](key1,key2)). This is actually what is done for C++ or Java sets :
template < class T, // set::key_type/value_type *class Compare = less<T>*, // set::key_compare/value_compare class Alloc = allocator<T> > // set::allocator_type > class set;
- A remark of minor importance : if distinct-values() is used to select
keys, the map:module shouldn't accept sequences as keys ? If I try a map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.
I guess you answered your own question? ;)
:) not really. My sentence was not correct, I meant "shouldn't the map:module accept sequences as keys ?" : since the baseX map:module is distinct-value based, it should work with sequences as keys.
2013/11/18 Christian Grün christian.gruen@gmail.com
- might this mechanism not be a little bit misleading ? Indeed, I was
expecting somehow that map:key(map:new({<node>:""})) to be an identity
for
<node>.
You’ve got me stumped here. The talk@xquery.com mailing list may be the best place to get more details on this.
- A remark of minor importance : if distinct-values() is used to select
keys, the map:module shouldn't accept sequences as keys ? If I try a map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.
I guess you answered your own question? ;)
All the best, Christian
Hi
I have an information, that could be interesting for others and a question about BaseX map:module.
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. Notice also that the heavy work is an implementation of Red Black Tree (at my knowledge, the standard technology for maps in imperative language), kindly provided here https://github.com/jpcs/rbtree.xq.
2) A question about the BaseX map module : what kind of tree technology is used behind ? (the standard Java RBtree ?). If you don't know, could you be kind enough to provide me a link to the implementation at BaseX repository ? Thanks in advance.
Cheers
2013/11/18 jean-marc Mercier jeanmarc.mercier@gmail.com
You’ve got me stumped here. The talk@xquery.com mailing list may be the best place to get more details on this.
I will try to post to this mailing list, thanks for the link. Indeed I started to implement through xquery a map version able to handle nodes for my needs. It is not obvious, because a map requires to define an equality properties over set. For nodes, deep-equal is a natural candidate, but it does not define an ordering, and performances are lost. For database nodes, it is possible to achieve this with internal (or maybe pre-database) ids, but I can't use it for dynamically created nodes. I guess that the best choice is to provide an optional binding to an external ordering function, something like *map:new**($maps as map(*)*, binding as map(*)) as map(*)* , where the binding provides an option to the ordering function (e.g. $order(key1,key2) := binding["order"](key1,key2)). This is actually what is done for C++ or Java sets :
template < class T, // set::key_type/value_type *class Compare = less<T>*, // set::key_compare/value_compare class Alloc = allocator<T> > // set::allocator_type > class set;
- A remark of minor importance : if distinct-values() is used to select
keys, the map:module shouldn't accept sequences as keys ? If I try a map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.
I guess you answered your own question? ;)
:) not really. My sentence was not correct, I meant "shouldn't the map:module accept sequences as keys ?" : since the baseX map:module is distinct-value based, it should work with sequences as keys.
2013/11/18 Christian Grün christian.gruen@gmail.com
- might this mechanism not be a little bit misleading ? Indeed, I was
expecting somehow that map:key(map:new({<node>:""})) to be an identity
for
<node>.
You’ve got me stumped here. The talk@xquery.com mailing list may be the best place to get more details on this.
- A remark of minor importance : if distinct-values() is used to select
keys, the map:module shouldn't accept sequences as keys ? If I try a map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.
I guess you answered your own question? ;)
All the best, Christian
- 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?
- 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/ba...
Christian
Sounds interesting. Have you thought about making it public to get 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 :)
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
- 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?
- 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/ba...
Christian
Sounds interesting. Have you thought about making it public to get 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 :)
That would be fast anyway… I’m looking forward to the result! 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
- 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?
- 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/ba...
Christian
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-Marc
2013/11/21 Christian Grün christian.gruen@gmail.com
Sounds interesting. Have you thought about making it public to get 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 :)
That would be fast anyway… I’m looking forward to the result! 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
- 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?
- 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/ba...
Christian
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 helps
Cheers,
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-Marc
2013/11/21 Christian Grün christian.gruen@gmail.com
Sounds interesting. Have you thought about making it public to get 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 :)
That would be fast anyway… I’m looking forward to the result! 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
- 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?
- 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/ba...
Christian
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 :
- 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 helps
Cheers,
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-Marc
2013/11/21 Christian Grün christian.gruen@gmail.com
Sounds interesting. Have you thought about making it public to get 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 :)
That would be fast anyway… I’m looking forward to the result! 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
- 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?
- 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/ba...
Christian
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 :
- 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 helps
Cheers,
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-Marc
2013/11/21 Christian Grün christian.gruen@gmail.com
Sounds interesting. Have you thought about making it public to get 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 :)
That would be fast anyway… I’m looking forward to the result! 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/ba...
Christian
Hi,
Casewhere someone is using these files, here is a more stable version, including some quite handy union, intersection and except "operators". By stable I mean that I am using them extensively since some weeks without any modifications ! Cheers
Jean-Marc
2013/12/8 jean-marc Mercier jeanmarc.mercier@gmail.com
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 :
- 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 helps
Cheers,
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-Marc
2013/11/21 Christian Grün christian.gruen@gmail.com
>Sounds interesting. Have you thought about making it public to get > 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 :)
That would be fast anyway… I’m looking forward to the result! 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/ba...
> > Christian
basex-talk@mailman.uni-konstanz.de
-
Christian Grün -
jean-marc Mercier