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
.
- Transform unique numbers to digits base n (length of unique numbers)
- Transform original list to digits base n
- 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