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

[Ghislain Fourny]

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