Re: Growing ordered set

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

On Fri, Nov 21, 2014 at 12:18:29PM +0100, Bill Allombert wrote:
> On Fri, Nov 21, 2014 at 01:04:26AM +0100, Karim Belabas wrote:
> 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.

To give an example, the attached C file implement a function treeadd()
that can be used in GP as follow:

test(n)=
{
  my(T=List());
  while(1,
   my(u,p);
   u=random(n);
   p=treeadd(T,u);
   if(p,break));
  T
}

? setrand(1);#test(10^11)
%1 = 537776
? ##
  ***   last result computed in 1,076 ms.

Cheers,
Bill

/*-*- compile-command: "/usr/bin/gcc -c -o ../tree.gp.o -O3 -Wall -fno-strict-aliasing -fomit-frame-pointer -fPIC -I"/home/bill/pari/amd64/include" ../tree.gp.c && /usr/bin/gcc -o ../tree.gp.so -shared -O3 -Wall -fno-strict-aliasing -fomit-frame-pointer -fPIC -Wl,-shared ../tree.gp.o -lc -lm -L/home/bill/pari/amd64/lib -lpari"; -*-*/
#include <pari/pari.h>
/*
GP;install("treeadd","lWGD1,L,","treeadd","./tree.gp.so");
*/
long treeadd(GEN T, GEN x, long i/*=1*/);
/*End of prototype*/

long
treeadd(GEN T, GEN x, long i/*=1*/)
{
  GEN p1 = gen_0, v;
  GEN w;	  /* vecsmall */
  long l, r;
  GEN d = list_data(T);
  if (!d)
  {
    listput(T, mkvec2(x, mkvecsmall2(0,0)), 0); /*update d!*/
    return 0;
  }
  p1 = gel(d, i);
  v = gel(p1, 1); w = gel(p1, 2);
  l = w[1]; r = w[2];
  if (gequal(x, v))
    return i;
  else
  {
    if (gcmp(x, v) < 0)
    {
      if (l)
        return treeadd(T, x, l);
      else
      {
        listput(T, mkvec2(x, mkvecsmall2(0,0)), 0); /*update d!*/
        d = list_data(T);
        mael3(d,i,2,1) = lg(d)-1;
      }
    }
    else
    {
      if (gcmp(x, v) > 0)
      {
        if (r)
          return treeadd(T, x, r);
        else
        {
          listput(T, mkvec2(x, mkvecsmall2(0,0)), 0); /*update d!*/
          d = list_data(T);
          mael3(d,i,2,2) = lg(d)-1;
        }
      }
    }
  }
  return 0;
}