[xquery-talk] From map entry pairs to a pair of arrays

[Christian Grün]

Hi Ghislain,

I completely agree with your assessment. I would expect the two writings…

  $map?*
  map:for-each($map, function($key, $value) { $value })

…to be faster than…

  $key ! map:get($map, $key)
  $key ! $map($key)

…because the latter ones require one additional lookup per key.
However, from a practical perspective, this is mostly up to the
implementation, which may choose different evaluation strategies for
each of the alternatives. For example, the evaluation of $map?* or
$map($key) could possibly be sped if it can statically be detected
that $map will always be of type map(*).

All the best,
Christian


On Mon, Jul 17, 2017 at 8:31 AM, Ghislain  Fourny <gfourny at inf.ethz.ch> wrote:
> Hi,
>
> My first (naive) thought reading this thread is that, from a theoretical complexity perspective -- unless I missed something -- the first version in the original message was already asymptotically optimal (linear). The time it takes to compute an output always has, as a lower bound, the time it takes to output it ("print it out"), and the output is made of two "passes of the input". The improvements suggested should change the constant, but asymptotically on larger inputs, I do not expect a significant difference.
>
> Having said this, of course, in practice, the constant may make a big difference.
>
> Just my two cents!
>
> Kind regards,
> Ghislain
>
>
>> On 16 Jul 2017, at 23:58, Michael Kay <mike at saxonica.com> wrote:
>>
>> ce between C and Assembly is a lot smaller than between C and XQ, and I think memory management should not be taken lightly (I'm not saying you do). In OP's case, I believe keys could be discarded while memory layout remains intact.
>>
>>
>> As a general rule of thumb, a lower-level language performs better provided that you have the time and skills to write the code efficiently.
>>
>> And as a general rule of thumb, you don't.
>>
>> Even when you are quite convinced that you do.
>>
>> It's a long time since I wrote in anything as low-level as C or assembler, but if you compare XQuery and Java, the level of abstraction of the API for maps is very similar, so there is no intrinsic reason to believe one should perform better than the other. The main difference is that maps in XQuery are immutable, which means you pay a little more for some operations (like adding a new entry), and you pay a lot less for other operations (llike bulk copying).
>>
>> Michael Kay
>> Saxonica
>> _______________________________________________
>> talk at x-query.com
>> http://x-query.com/mailman/listinfo/talk
>
>
> _______________________________________________
> talk at x-query.com
> http://x-query.com/mailman/listinfo/talk