# Is there a readymade Array Type that stores data as Run-length-encoding of delta?

**URL:** <https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793>\
**Category:** General Usage\
**Created:** [June 30, 2021, 3:12am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793 "2021-06-30T03:12:55Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 30, 2021, 3:12am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/1 "2021-06-30T03:12:55Z")

</div>

I wonder in Julia, is there a ready-made array type that stores data internally as run-length-encoded deltas?

E.g.

This is literally a question from a colleague working in Python. I am not sharing any secrets as it’s just a general question about Python. And you can see that you can store data much more efficiently if you just delta it and then RLE it.

I know there is RLE vectors. But I think this is quite a common problem in TimeSeries so I am wondering if there’s a ready-made vector type so I don’t have to make it myself 🙂

> General question:  
> Assume I have some very large vector, but the actual count of _unique_ values is very low.  
> e.g.: `[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]` Obviously, one can greatly reduce the memory required to represent this vector given the unique values and the fact that they come in consecutive blocks.So my question is: Is there some mechanism in `numpy` or `scipy` or other thing that supports these `array-like` structures but with efficient storage in memory?"

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [June 30, 2021, 4:14am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/2 "2021-06-30T04:14:56Z")

</div>

Something like `sparse([first(x), diff(x)...])`?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 30, 2021, 5:41am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/3 "2021-06-30T05:41:10Z")

</div>

`x = sparse([first(x), diff(x)...])`

But now

`x[2]` will give `0` instead of `1`

The point is that the the `sparse` one is just the internal rep that user doesn’t see.  
It’s internally stored very efficiently but what the user sees is just `[1,1,....,2,.....3,...]` so no different to a normal array.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [June 30, 2021, 6:03am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/4 "2021-06-30T06:03:50Z")

</div>

It would be interesting to see applications which uses such a representation, because while memory efficient, `getindex` and `setindex` will be very slow, compared to usual array manipulations. Only in a very special cases this representation can provide some benefits, e.g. when you are not mutating vector and only iterate over it.

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [June 30, 2021, 6:03am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/5 "2021-06-30T06:03:55Z")

</div>

Yeah, you would need

```julia
struct DiffVector <: AbstractVector
x::SparseVector
DiffVector(x) = new(sparse([first(x), diff(x)...]))
end

getindex(x::AbstractVector, i) = sum(x.x[1:i])

```

or something. Sorry, the real answer is I don’t know of any ready made implementations, this is how I would start implementing it.

---

<div class="post-metadata">

**Author:** ![jishnub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jishnub/32/33620_2.png) [@jishnub](https://discourse.julialang.org/u/jishnub)\
**Post date:** [June 30, 2021, 8:18am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/6 "2021-06-30T08:18:18Z")

</div>

Perhaps [RLEVectors.jl](https://github.com/phaverty/RLEVectors.jl) might be relevant, although I wonder if this is something that you have already considered?

```julia
julia> v = RLEVector([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3])
RLEVector{Int64, Int64}
 Run values: [1, 2, 3]
 Run ends: [30, 175, 208]

julia> v[30]
1

julia> v[31]
2

```

I’m not familiar with the package though

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 30, 2021, 11:03pm UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/7 "2021-06-30T23:03:14Z")

</div>

> [@jishnub](#):
>
> Perhaps [RLEVectors.jl](https://github.com/phaverty/RLEVectors.jl)

I had mentioned that it could help. I guess it doesn’t exists yet such a package.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 30, 2021, 11:54pm UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/8 "2021-06-30T23:54:47Z")

</div>

Built a MVP

```julia
using RLEVectors

mutable struct DiffRLEVector{T} <: AbstractVector{T}
    _orig_val::T
    _arr::RLEVector{T}
    DiffRLEVector(v::AbstractVector{T}) where T = new{T}(v[1], RLEVector(diff(v)))
end

import Base

function Base.getindex(v::DiffRLEVector, i::Integer)
    i == 1 ? v._orig_val : v._orig_val + sum(v._arr[1:i-1])
end

function Base.size(v::DiffRLEVector)
    (1 + size(v._arr)[1], )
end

v = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]

dv = DiffRLEVector(v)

Base.summarysize(v)
Base.summarysize(dv) # much smaller

v == dv #true

```

BTW this is surprisingly hard to do in python. Probably because no one has one a rle vector type and extending numpy’s array seems very convoluted process.

---

<div class="post-metadata">

**Author:** ![anon56330260](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@anon56330260](https://discourse.julialang.org/u/anon56330260)\
**Post date:** [July 1, 2021, 7:19am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/9 "2021-07-01T07:19:22Z")

</div>

I guess OpenVDB might be helpful here, it’s a hierarchical fixed-size array mainly designed for representation of signed distance field, something like quad-tree. It supports for constant-time getindex and setindex!. I currently try to port it to Julia, but still in progress.

---

<div class="post-metadata">

**Author:** ![anon56330260](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@anon56330260](https://discourse.julialang.org/u/anon56330260)\
**Post date:** [July 1, 2021, 7:34am UTC](https://discourse.julialang.org/t/is-there-a-readymade-array-type-that-stores-data-as-run-length-encoding-of-delta/63793/10 "2021-07-01T07:34:12Z")

</div>

Actually, a quick (and bad performance) constant-time implementation will be:

```julia
const FixedSize = 16
# A compressed string with length FixedSize, if it consists of only one unique character, then we represent it by a Char to save memory 
struct CompressedString
    val::Union{String,Char}
end

struct RLEString
    s::Dict{Index,CompressedString}
end

function getindex(s::RLEString,i) 
    cs = s.s[i>>4]
    if isa(cs.val,Char)
         return cs.val
    else
         return cs.val[i & (FixedSize-1)]
    end
end

```