Ruud H.G. van Tol on Thu, 29 Dec 2022 18:45:09 +0100

 Re: veccount

```
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

```

• References:
• veccount
• From: "Ruud H.G. van Tol" <rvtol@isolution.nl>
• Re: veccount
• From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
• Re: veccount
• From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>