Charles Greathouse on Wed, 04 Jan 2017 23:12:02 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Search a VECSMALL?


That's a significant speedup which users can't easily get in GP, so I'm all for it. I agree that set functions should not be obligated to support any types other than t_VEC, but where it makes sense I don't see any harm.

Charles Greathouse
Case Western Reserve University

On Wed, Jan 4, 2017 at 2:24 PM, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:
* Charles Greathouse [2016-11-27 23:03]:
> setsearch and vecsearch don't work on vecsmall. Is there some other command
> that works on them? (If not, I have a feature request.)

I somehow missed that post, sorry.

I just reviewed that code and made the necessary minimal changes for
vecsort and vecsearch to officially work on t_VECSMALLs in 'master'
- vecsort: already there, just changed the documentation :-)
- vecsearch: already there, just prevented from working by 3 different
  typos in 2 lines; now working and documented as well.

In both cases, a "comparison function" argument (cmpf) is not allowed:

? v = vecsort(Vecsmall([5,2,3,-1]))
%1 = Vecsmall([-1, 2, 3, 5])
? vecsearch(v, 4)
%2 = 0
? vecsearch(v, 5)
%3 = 4
? vecsort(Vec(v), (a,b)->sign(b-a))
%4 = [5, 3, 2, -1]
? vecsort(v, (a,b)->sign(b-a))
  ***   at top-level: vecsort(v,(a,b)->sig
  ***                 ^--------------------
  *** vecsort: incorrect type in sort_function (t_VECSMALL).


I'm not sure I want to support t_VECSMALLs in "set" functions; so far only
t_VEC is support, except in setsearch which also allows t_LIST. OTOH,
it's trivial to add on top of the existing sorting function and that
would speed up sets of small integers by a factor 3 in GP (and slash
memory use by the same factor).

Opinions ?

Best wishes for the new year,

    K.B.
--
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]
`