Hello,
Thank you for the rewrote of the memoize function, that's very interesting. (and the part about the java hashmap will actually find a use for another problem I have).
My goal was to get faster results when a query is run multiple times. Yes, that's probably premature optimization, but since I do require these things in other application stacks I thought I'd ask.
Mickaël
----- Mail original ----- De: "Christian Grün" christian.gruen@gmail.com À: "Andreas Mixich" mixich.andreas@gmail.com, "Mickael Desfrenes" mickael.desfrenes@unicaen.fr Cc: "basex-talk" basex-talk@mailman.uni-konstanz.de Envoyé: Mercredi 8 Avril 2020 11:05:46 Objet: Re: [basex-talk] Memoize
Hi Mickael, hi Andreas,
It is written in the Marklogic dialect of XQuery. but porting it was a no-brainer, since, AFAIR, only the syntax for maps had to be changed. The Github repo is here.
I see that the code uses MarkLogic’s map module functions, which are based on an implementation of a classical side-effecting and mutable hash map. As real XQuery maps are immutable (i.e., once defined, their contents will never change, see [1]), you may need to use Java bindings and instantiate a Java HashMap [2]. I have rewritten one of the proposed memoize functions, it’s attached.
I forgot to mention that BaseX itself uses runtime optimizations to memoize data as well. Just two examples:
1. If a path expression is requested multiple times, its result will automatically be cached. In the query below, it’s //name that will only be evaluated once:
//city[. = //name]
2. If large sequences are compared, the items to be compared will incrementally be stored in a hash map. In the query below, it’s the items of $lines2 that will be put to a hash map:
let $lines1 := file:read-text-lines('file1.txt') let $lines2 := file:read-text-lines('file2.txt') return $lines1[. = $lines2]
In both cases, evaluation time can be reduced from a quadratical to a linear runtime (and the result may be available within milliseconds instead of seconds or minutes).
@Mickael:
1. Do you try to reduce the runtime of specific queries, or 2. do you want to get faster results if you run the same query multiple times?
Do you possibly have specific use cases or queries which you’d like to speed up via memoization?
Best, Christian
[1] http://docs.basex.org/wiki/XQuery_3.1#Maps [2] http://docs.basex.org/wiki/Java_Bindings