Re: vecsort() and sign()

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Karim Belabas [2018-02-20 22:18]:
> * Bill Allombert [2018-02-20 14:59]:
>> On Tue, Feb 20, 2018 at 11:27:12AM +0100, Karim Belabas wrote:
>> We could also allow cmpf to be a closure with arity 1 and then use
>> (x,y)->cmp(cmpf(x),cmpf(y)) as a comparaison function.
> 
> Nice idea. But the documentation gives an example which explains
> why a naive implementation of this is a bad idea (n log(n) calls to cmpf
> instead of n).
> 
> In this case, it is better to do something like
> 
>   T = [cmpf(x) | x<-v];
>   perm = vecsort(T,,1); \\ indirect sort
>   vecextract(v, perm)
> 
> We can do that internally, of course. I have a quick & dirty
> implementation for this.

Now cleanup up and committed to master !

Cheers,

    K.B.

P.S.
> Unfortunately, the idea breaks down with vecsearch(), which is a most
> important application of vecsort() [ for repeated searches in a sorted
> vector ]:
[...]
> Still wondering whether there's a simple solution...

I ended up documenting the more efficient (but cumbersome) solution. Of
course it's no worse than the current situation. If speed is critical,
using a non-trivial "comparison function" in vecsearch is never a good idea.

--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`