Re: veccount

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

On 2022-12-29 15:16, Karim Belabas wrote:
> * Ruud H.G. van Tol [2022-12-29 13:04]:
> > ? binary(92)
> > %3 = [1, 0, 1, 1, 1, 0, 0]
> >
> > How to effectively transform that to [1,1,3,2] (run-lengths),
> > and next to 3 (the number of different run-length values)?
> > [...] a condensed way from binary(92) to 3 would already help,
> Something like
>
>    /* assume v is a non-empty vector */
>    rlev(v) =
>    { my(x = v[1], c = 1, L = List());
>      for (i = 2, #v, if (v[i] == x, c++, listput(L,c); x = v[i]; c = 1));
>      listput(L,c); #Set(L);
>    }
>
>    ? rlev(binary(92))
>    %2 = 3
>
>    ? setrand(1); v = vector(10^6, i, random(2));
>    ? rlev(v)
>    time = 894 ms.
>    %4 = 20
>
> One can save a log factor by using a counting sort to replace the list L
> and final #Set(L):
>
>    /* assume v is a non-empty vector */
>    rlev2(v) =
>    { my(x = v[1], c = 1, w = vector(#v));
>      for (i = 2, #v, if (v[i] == x, c++, w[c] = 1; x = v[i]; c = 1));
>      w[c] = 1; hammingweight(w);
>    }
>
>    ? rlev2(v)
>    time = 437 ms.
>    %5 = 20

That led me to write it as:


rlev3(v) =

{ my( w= vector(#v), p= 1 );
  for(i= 2, #v, if(v[i] != v[i-1], w[i - p]= 1; p= i));
  w[#v + 1 - p]= 1;
  hammingweight(w);
}


-- Ruud