Re: Growing ordered set

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Nov 21, 2014 at 01:04:26AM +0100, Karim Belabas wrote:
> > binary search tree:
> > 
> > ? setrand(1);test(10^11)[1]
> > %1 = 537777
> > ? ##
> >   ***   last result computed in 9,325 ms.
> > 
> > listinsert:
> > 
> > ? setrand(1);test2(10^11)[1]
> > %2 = 537777
> > ? ##
> >   ***   last result computed in 43,584 ms.
> 
> That's beautiful, indeed, but...
> 
>   (00:48) gp > install(test3,lG)
>   (00:48) gp > setrand(1); test3(10^11)
>   time = 220 ms.
>   %2 = 537777

Well, but writing everything in C is cheating...

Running my code through gp2c leads

? setrand(1);#test(10^11)
%1 = 537776
? ##
  ***   last result computed in 1,484 ms.
? setrand(1);#test2(10^11)
%2 = 537776
? ##
  ***   last result computed in 41,908 ms.

Thus we could provide a C interface to t_LIST trees that would be not much slower
than your code.

Cheers,
Bill.