Re: vecsort() and sign()

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

* Bill Allombert [2018-02-20 14:59]:
> On Tue, Feb 20, 2018 at 11:27:12AM +0100, Karim Belabas wrote:
> > Done ! In fact, this is a rather useless construct since it's trivial to
> > emulate it with (x,y)->x[k]-y[k]. A much more useful one is k = [1,3,2]
> > (sort by 1st entry, then 3rd, then 2nd: this one is more painful to emulate
> > with a closure...).
> 
> 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.

Unfortunately, the idea breaks down with vecsearch(), which is a most
important application of vecsort() [ for repeated searches in a sorted vector ]:
I can not re-use the array of precomputed values because vecsort has no way of
making it available. So the vecsearch implementation for arity 1 closures is
silly compared to what the user could do in 3 lines as above +

  T = vecextract(T, perm); \\ sorted precomputed values
  vecsearch(T, cmpf(x)) 

(and variants thereof). So, the implementation ends up making O(log n) calls to
cmpf for each search, whereas all necessary values should already be
available (except cmpf(x) itself).

Still wondering whether there's a simple solution...

Cheers,

    K.B.

P.S. While implementing the above, I found a problem in my earlier
answer, due to a historical bug: the arity 2 closure *must* [currently]
return an integer, else it is considered invalid. Hence the need for sign()
for non-integral comparison functions ...

I've committed a fix for this bug so that the earlier explanation
becomes 100% valid :-).
 
--
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]
`