Support for low-complexity (compressible) lists

No, I do not believe there is built-in functionality for the data form you describe.

However Interpolation comes close. Here's an example.

in = {17, 17, 17, 17, 17, 21, 21, 21, 21, 21, 21, 21, 21, 11, 11, 11, 11, 11, 11, 
   11};

sa = SparseArray @ Differences @ Prepend[in, 0];
p = sa["AdjacencyLists"]
v = in[[p]]

f = Quiet@*Interpolation[
    Join[{p - 1, RotateRight@v}\[Transpose], {{Last@p, Last@v}}], 
    InterpolationOrder -> 0];

in === Array[f, Length@in]
{1, 6, 14}

{17, 21, 11}

True

So this gives a function f which returns the element of in for a given index.

We can also pull spans from the SparseArray (assigned to sa) like this:

in[[10 ;; 15]]

Accumulate @ sa[[10 ;; 15]] + f[10]
{21, 21, 21, 21, 11, 11}

{21, 21, 21, 21, 11, 11}

For large extractions this is much faster than using the InterpolatingFunction (f). Using the code above but starting with:

SeedRandom[0];
in = Join @@ ConstantArray @@@ RandomInteger[{1, 99}, {5000, 2}];

Then:

(r1 = Accumulate@sa[[100000 ;; 150000]] + f[100000];)   // RepeatedTiming
(r2 = f @ Range[100000, 150000];)                       // RepeatedTiming

r1 === r2
{0.000696, Null}

{0.0527, Null}

True

 {First[#], Length[#]}& /@ 
 Split[{17, 17, 17, 17, 17, 21, 21, 21, 21, 21, 21, 21, 21, 11, 11, 11, 11, 11, 11, 11}]

(*

{{17, 5}, {21, 8}, {11, 7}}

*)

{First[#], Length[#]}& /@ 
Split[ {0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, -10, 0, 0, 0, 0, 0, 0}]

(*

{{0, 4}, {4, 1}, {0, 7}, {-10, 1}, {0, 6}}

*)

@J.M. points out that it is simpler to use Split than SplitBy.


  1. Transform unique numbers to digits base n (length of unique numbers)
  2. Transform original list to digits base n
  3. Construct an integer from the list of it's digits base n

Using integer instead of a list of numbers uses much less memory. (1 : 10)

In:

Clear[xs, ys, number, rules]
ToNumber[xs_] := Module[{uniques, base, digits, rules, number},
  uniques  = Union[xs];
  base = Length[uniques];
  digits = Range[0, base - 1];
  rules = Thread[Rule[uniques, digits]];
  number = FromDigits[(xs /. rules), base];
  {number, base, Map[Reverse, rules]}
  ]

xs = RandomChoice[Range[0, 19]*5, 10^2];
{number, base, rules} = ToNumber[xs]

ys = IntegerDigits[number, base] /. rules

(* Test *)
xs == ys

(* Memory *)
xs // ByteCount
number // ByteCount

Out:

{60, 75, 60, 20, 70, 30, 5, 5, 15, 90, 75, 90, 0, 50, 35, 80, 30, 15, \
25, 70, 65, 90, 5, 25, 35, 20, 65, 40, 80, 15, 20, 40, 45, 95, 50, \
70, 55, 35, 5, 70, 10, 90, 55, 85, 25, 25, 95, 90, 85, 20, 80, 55, \
45, 35, 75, 25, 30, 5, 5, 30, 65, 80, 25, 85, 35, 35, 50, 75, 0, 20, \
65, 85, 40, 35, 25, 55, 65, 20, 75, 60, 0, 50, 60, 80, 10, 35, 5, 5, \
5, 75, 60, 65, 25, 10, 10, 30, 25, 55, 90, 90}

{810066090674088052770306597191253060527186521556149860642933055414395\
7285417316417930562947049000100525456920489251180883335404778, 
20, 
{0 -> 0, 1 -> 5, 2 -> 10, 3 -> 15, 4 -> 20, 5 -> 25, 6 -> 30, 7 -> 35, 
  8 -> 40, 9 -> 45, 10 -> 50, 11 -> 55, 12 -> 60, 13 -> 65, 14 -> 70, 
  15 -> 75, 16 -> 80, 17 -> 85, 18 -> 90, 19 -> 95}}

 {60, 75, 60, 20, 70, 30, 5, 5, 15, 90, 75, 90, 0, 50, 35, 80, 30, 15, \
25, 70, 65, 90, 5, 25, 35, 20, 65, 40, 80, 15, 20, 40, 45, 95, 50, \
70, 55, 35, 5, 70, 10, 90, 55, 85, 25, 25, 95, 90, 85, 20, 80, 55, \
45, 35, 75, 25, 30, 5, 5, 30, 65, 80, 25, 85, 35, 35, 50, 75, 0, 20, \
65, 85, 40, 35, 25, 55, 65, 20, 75, 60, 0, 50, 60, 80, 10, 35, 5, 5, \
5, 75, 60, 65, 25, 10, 10, 30, 25, 55, 90, 90}

True
936
96