# Sparse set-like indexible data structure
**URL:** https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525
**Category:** General Usage
**Tags:** question
**Created:** [October 18, 2017, 2:50pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525 "2017-10-18T14:50:20Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@Ward9250](https://discourse.julialang.org/u/Ward9250)
#### Post date: [October 18, 2017, 2:50pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/1 "2017-10-18T14:50:20Z")
I have a need for a data type in my code which is set-like, so stores only unique values, and can efficiently do intersections and unions and such, but that can also be indexed, and is efficient for sparse sets.
My possible values are 1 - 64, but I will only ever have a few - rarely more than 4 of those possible values, in any one set. Is there a data structure in julia base or a package which is well suited to those requirements?
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [October 18, 2017, 3:17pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/2 "2017-10-18T15:17:07Z")
Can you be more specific about indexing? Would any stable mapping from integers to elements do, or do you want sorting, indexing by insertion order, etc? A MWE would clarify things. That said, the first place I would look is
> **[GitHub - JuliaCollections/DataStructures.jl: Julia implementation of Data...](https://github.com/JuliaCollections/DataStructures.jl)**
>
> Julia implementation of Data structures. Contribute to JuliaCollections/DataStructures.jl development by creating an account on GitHub.
---
### Author:  [@Ward9250](https://discourse.julialang.org/u/Ward9250)
#### Post date: [October 18, 2017, 3:28pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/3 "2017-10-18T15:28:35Z")
Specifically I want to index by integer because I want to work with all of the pairs of values that are possible in the set.
In an `i = 1:length(myset), j = (i+1):endof(set)` sort of way.
If I want to so that with Set in Base, I have to collect into an array and then work with the array. But I don’t want the extra array allocation, because I’m going to be building these small sets and doing this operation with them a huge number of times.
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [October 18, 2017, 3:43pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/4 "2017-10-18T15:43:00Z")
Perhaps you have already considered this, but you can iterate on a `Set`. It does not construct an intermediate vector, just traverses the elements (same mechanism that traverses a `Dict`, since `Set` is implemented as a special case of that).
---
### Author:  [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)
#### Post date: [October 18, 2017, 4:36pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/5 "2017-10-18T16:36:58Z")
If you know your values to be integers from 1 to 64, you could use a sparse Boolean vector of length 64, which holds `true` value only for the indices mapping the elements in the set. The union is then just element-wise `||` and the intersect is element-wise `&&`, and all the values in the set will be stored in the field `nzind` sorted! I guess the least efficient bit is adding or removing elements from the middle of the vector but for small vectors, it may not be a problem.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [October 18, 2017, 5:06pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/6 "2017-10-18T17:06:06Z")
This sounds a lot like a slightly more specialized IntSet. You can avoid much of the overhead since all your values fit into a single `UInt64` bit mask, and even though indexing would have to be O(N), N is _really_ small. Range subsetting is even easier — it’s just bitwise and with an appropriately constructed mask.
[https://github.com/JuliaLang/julia/blob/master/base/intset.jl](https://github.com/JuliaLang/julia/blob/master/base/intset.jl)
---
### Author:  [@Ward9250](https://discourse.julialang.org/u/Ward9250)
#### Post date: [October 18, 2017, 5:57pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/7 "2017-10-18T17:57:41Z")
I’ve been thinking it sounds like a very small bit-vector.
The issue for me whilst a 64bit number will store which ints are in the set.
When I want to get the nth value present in the set I have to iterate through each bit until I get to the nth 1 bit. Which in a sparse set is not great, it’s 64 iterations in the worst case for this situation.
Which isn’t great especially given I’m going to have a lot of these small sets. I was wondering if the addition of some sort of index would make that operation faster.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [October 18, 2017, 6:09pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/8 "2017-10-18T18:09:47Z")
I think you’re overthinking it. These operations are _fast_. The difference between getting the first bit of an IntSet and the 64th bit of an IntSet is about a nanosecond. Doing anything more complicated adds more branches, more data, more code, and almost certainly more time.
```julia
julia> S = IntSet()
push!(S, 64)
IntSet([64])
julia> @btime first($S) # effectively worst case S[1]
29.776 ns (0 allocations: 0 bytes)
64
julia> push!(S, 1)
IntSet([1, 64])
julia> @btime first($S) # best case S[1]
28.748 ns (0 allocations: 0 bytes)
1
```
And this could be even faster were it simply using one `UInt64` instead of a BitVector.
---
### Author:  [@Ward9250](https://discourse.julialang.org/u/Ward9250)
#### Post date: [October 18, 2017, 7:07pm UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/9 "2017-10-18T19:07:32Z")
Ok thanks! I shall make a small type that does this for 64 values. Just weighing up whether to make it a mutable struct allocated and managed by the gc, or an immutable primitive type, given the number of them I’ll be creating and manipulating. Although I may be able to refactor to reuse the same instance of the mutable again and again.
---
### Author:  [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)
#### Post date: [October 19, 2017, 1:21am UTC](https://discourse.julialang.org/t/sparse-set-like-indexible-data-structure/6525/10 "2017-10-19T01:21:12Z")
You could also cache the Set values into a pre-allocated Array for faster indexed lookup. That way you only need the slower index into Set once.
Here’s an example to show what I mean:
Method 1: No caching - direct indexing into Set:
```julia
function Base.getindex(S::IntSet, i::Integer)
if 1 <= i <= length(S)
state = start(S)
x = 0
for j = 1:i
x, state = next(S, state)
end
return x
else
throw(BoundsError(S, i))
end
end
function pairstuff1(S::AbstractSet, isprint=false)
for i = 1:length(S), j = (i+1):length(S)
x1 = S[i]
x2 = S[j]
end
end
```
Method 2: Caching - index into Set once only, then index into pre-allocated Array
```julia
const A = Vector{Int}(64);
function pairstuff2(S::AbstractSet, isprint=false)
# populate array
i = 0
for x in S
i += 1
A[i] = x
end
# pairwise stuff
for i = 1:length(S), j = (i+1):length(S)
x1 = A[i]
x2 = A[j]
end
end
```
Now some benchmarking …
```julia
using BenchmarkTools
S = IntSet([5, 10, 15, 55])
@benchmark pairstuff1($S)
@benchmark pairstuff2($S)
```
On my machine, cached version is about 5 times faster.