map:module. Behavior of maps of nodes

> 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 > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk >

> 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 at 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>.

> - 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.

>You’ve got me stumped here. The talk at xquery.com mailing list may be > the best place to get more details on this.

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? ;)

> > - 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 at 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 > > [1] http://x-query.com/mailman/listinfo/talk >

> >You’ve got me stumped here. The talk at 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 at 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 at 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 >> >> [1] http://x-query.com/mailman/listinfo/talk >> > >

> 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.

> 2) A question about the BaseX map module : what kind of tree technology is > used behind ?

>Sounds interesting. Have you thought about making it public to get > more feedback?

>It’s an implementation of Phil Bagwell’s immutable hash tries (as >mentioned in your previous thread…):

> > 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 >

>>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 at 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 > >

> >>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 at 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 > > > > >

> 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 at 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 at 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 >> > >> > >> > >

On Fri, Dec 6, 2013 at 4:29 PM, jean-marc Mercier < jeanmarc.mercier at 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 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 at 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 at 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 at 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 >>> > >>> > >>> >> >> >

>thanks a lot for your profiling results and the attached XQuery modules

> 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 at 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 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 at 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 at 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 at 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 >>>> > >>>> > >>>> >>> >>> >> >

> 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 at 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 at 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 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 at 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 at 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 at 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 >>>>> > >>>>> > >>>>> >>>> >>>> >>> >> >