# Best data structure for fast unions of large sets of integers

**URL:** <https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785>\
**Category:** Performance\
**Tags:** performance, set, datastructures\
**Created:** [May 3, 2024, 10:32am UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785 "2024-05-03T10:32:04Z")\
**Posts on this page:** 17\
**Page:** 3

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 4, 2024, 1:29pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/42 "2024-05-04T13:29:20Z")

</div>

> [@Tarny\_GG\_Channie](#):
>
> You need to iterate through a union?

I need to iterate through the objects that represent my sets, but only at the very end of the procedure, so it’s not the time-consuming part.

> [@Tarny\_GG\_Channie](#):
>
> Do you need the union of multiple sets, or just a pair?

Unions will always be pairwise. Basically it’s about an operator overloading system where numbers are replaced by sets of integers, and all the usual operations are replaced by set unions. Don’t ask why it’s useful, trust @hill on this 😉

> [@Tarny\_GG\_Channie](#):
>
> Can you tolerate duplicate?

Yes but duplicates might slow down other unions further down the line, by making the sets bigger.

> [@sumiya11](#):
>
> Might be worth to try `C = vcat(A, B)` then

That’s actually a really nice and simple idea. If there are never any duplicates this is optimal, but I cannot know it ahead of time

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [May 4, 2024, 1:58pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/43 "2024-05-04T13:58:19Z")

</div>

I don’t see why not just keep a list (array,vector, etc) of sets that form the union. When you need to iterate through it, just iterate through each one and deduplicate with some mean.

Maybe even something like…

> struct UnionSet{T}  
> A::Set{T}  
> B::Set{T}  
> end

Union is really fast, just copying two pointers.

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [May 4, 2024, 2:09pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/44 "2024-05-04T14:09:46Z")

</div>

> [@gdalle](#):
>
> ```julia-auto
> return @belapsed union(A, B) setup = ( #
> A = $S(rand($universe, $set_size));
> B = $S(rand($universe, $set_size))
> ) seconds = 1
> 
> ```

Considering the problem, switching from `union` to `union!` is a big deal. Essentially, just one BitSet is needed.

As bears out when actually running benchmark with `union!`.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 4, 2024, 2:28pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/45 "2024-05-04T14:28:11Z")

</div>

> [@Tarny\_GG\_Channie](#):
>
> I don’t see why not just keep a list (array,vector, etc) of sets that form the union. When you need to iterate through it, just iterate through each one and deduplicate with some mean.

I thought about that but I feared it might make the memory requirements of the program scale linearly with its depth. Imagine that we’re doing this operator overloading with a neural network:

- If we create a new set at every operation, we can forget everything that happened in previous layers
- If we do it with pointers, we have to keep track of every array of pointers since the beginning

> [@Dan](#):
>
> Considering the problem, switching from `union` to `union!` is a big deal. Essentially, just one BitSet is needed.

That is an interesting insight!  
However, conceptually these set objects are used like numbers in the program due to operator overloading. And when I do `s1 + s2`, i can’t afford to modify either argument in case I need them somewhere else for `s1 + s3`. Basically, since numbers are usually not mutable, there seems to be no way to leverage the mutability of sets

---

<div class="post-metadata">

**Author:** ![sumiya11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sumiya11/32/207147_2.png) [@sumiya11](https://discourse.julialang.org/u/sumiya11)\
**Post date:** [May 4, 2024, 3:15pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/46 "2024-05-04T15:15:42Z")

</div>

If you are evaluating arithmetic expressions over sets then reordering the union operations would probably be beneficial

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [May 4, 2024, 4:21pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/47 "2024-05-04T16:21:47Z")

</div>

> [@gdalle](#):
>
> - If we create a new set at every operation, we can forget everything that happened in previous layers
> - If we do it with pointers, we have to keep track of every array of pointers since the beginning

I understand your concern but I’m actually thinking this is a very memory efficient way. Let’s say A is 1000 elements and B is 1000 elements, same with C and so on, if you create A|B, then you might get a new 2000 elements set. Now, if you create A|C, you might get another 2000 elements set. Now, even if you forgot A, B, and C, you still end up consuming a lot of extra memories. Compare this to just keeping a few pointers.

---

<div class="post-metadata">

**Author:** ![Janis\_Erdmanis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/janis_erdmanis/32/10869_2.png) [@Janis\_Erdmanis](https://discourse.julialang.org/u/Janis_Erdmanis)\
**Post date:** [May 4, 2024, 5:55pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/48 "2024-05-04T17:55:39Z")

</div>

I’m joining this discussion a bit late, but I think there might be a viable approach involving the idea of a bitset combined with run-length encoding in a bitvector which woulde address issues related to sparsity. To construct a union, one would need to iterate through both bitvectors to create a third one. However, a significant drawback is that this process requires handling elements individually rather than using bitwise operations which processes result in chunks of 64 bits, as is possible with a bitset.

One possible optimization to speed up the process involves handling large gaps in one set: bits from the other set can be ORed into the resulting set within these gaps. The main challenge here is determining where to stop copying, for which I can’t think of a neat solution.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 5, 2024, 5:05am UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/49 "2024-05-05T05:05:08Z")

</div>

> [@Tarny\_GG\_Channie](#):
>
> Now, even if you forgot A, B, and C, you still end up consuming a lot of extra memories. Compare this to just keeping a few pointers.

That’s fair. I guess it will depend on the specific application, and the depth of the computational graph. I’ll implement it to see

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 5, 2024, 5:05am UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/50 "2024-05-05T05:05:57Z")

</div>

> [@Janis\_Erdmanis](#):
>
> with run-length encoding in a bitvector which woulde address issues related to sparsity

I’m not sure I understand what you mean

---

<div class="post-metadata">

**Author:** ![Janis\_Erdmanis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/janis_erdmanis/32/10869_2.png) [@Janis\_Erdmanis](https://discourse.julialang.org/u/Janis_Erdmanis)\
**Post date:** [May 5, 2024, 9:43am UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/51 "2024-05-05T09:43:09Z")

</div>

It is similar to listing out indices when one occurs. The run-length encoding lists the 0s between every one and encodes them in the bit vector. This is generally used as a simple compression strategy when the only known thing about the bivector is that it is sparse.

A very crude implementation is [here](https://github.com/PeaceFounder/PeaceFounder.jl/blob/master/src/Utils/BitCompressor.jl). I see a benefit if there are long gaps in one of the sets. If another set has many elements, the union would require copying the bits into the resulting bit vector from it directly, which can be done in chunks and thus could be faster than pushing individual integers into a vector. To have such optimisation, though, one would need to encode information on how many bits a given chunk represents.

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [May 5, 2024, 2:25pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/52 "2024-05-05T14:25:39Z")

</div>

> [@sumiya11](#):
>
> Might be worth to try `C = vcat(A, B)` then

I too had thought of an approximate solution like this.  
I propose a less brutal, albeit slower, one.

```julia
[A;deleteat!(B,findall(!isnothing,indexin(B,A)))]

```

If I have not misunderstood, the operations to be performed are simply the union of a set of values.  
Something along the following lines could be adopted

```julia

A = Set(rand(1:universe_size, set_size))
B = Set(rand(1:universe_size, set_size))
C = rand(1:universe_size, set_size)

function byteset_un(v1::Array, v2::BitArray=falses(10^6))
    for b in v1
        v2[b]=true
    end
    v2
end

byteset_un(v1::Array, v2::Array) = byteset_un(v2,byteset_un(v1))

byteset_un(v1::BitArray, v2::BitArray) = v1 .| v2

byteset_un(A,B)

bA=byteset_un(A)

bB=byteset_un(B,bA)
bC=byteset_un(C,bB)

bAB=byteset_un(bA,bA)

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 6, 2024, 4:57pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/53 "2024-05-06T16:57:01Z")

</div>

See this new topic for a discussion of the recursive set idea, if the performance nerds are not tired yet!

> [@Can I speed up this recursive set implementation?](https://discourse.julialang.org/t/can-i-speed-up-this-recursive-set-implementation/113917):
>
> Hey there! I come to you with another performance nerdsnipe, whose solution could have a big impact on the autodiff ecosystem (via SparseConnectivityTracer.jl and DifferentiationInterface.jl). You may remember my first question on pseudo-set data structures for fast unions: One interesting proposal from that discussion (thanks @Tarny_GG_Channie) is a lazy set union, containing only pointers to the two sets it unites. I want to see how fast we can make this approach. The code below is a sim…

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 6, 2024, 6:11pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/54 "2024-05-06T18:11:27Z")

</div>

I’m also very late to this party. Is the [union-find data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) useful for this application?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 6, 2024, 6:13pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/55 "2024-05-06T18:13:16Z")

</div>

I don’t think so because I am not sure that the sets I `union` will be _disjoint_ (in fact, I’m pretty sure they won’t be in most cases)

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 6, 2024, 6:14pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/56 "2024-05-06T18:14:38Z")

</div>

I don’t think that’s a requirement, just an internal property of the data structure.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [May 6, 2024, 6:20pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/57 "2024-05-06T18:20:49Z")

</div>

> [@gdalle](#):
>
> I don’t think so because I am not sure that the sets I `union` will be _disjoint_ (in fact, I’m pretty sure they won’t be in most cases)

I’d assume it’s faster to make them disjoint than it would be to merge them for most use-cases though right? e.g.

```julia-auto
julia> let sets = (Set([1,2]), Set([2, 3, 4]), Set([4, 5, 6]))
           for i ∈ 1:(length(sets)-1)
               setdiff!(sets[i], sets[i+1:end]...)
           end
           sets
       end
(Set([1]), Set([2, 3]), Set([5, 4, 6]))

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 6, 2024, 6:23pm UTC](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785/58 "2024-05-06T18:23:10Z")

</div>

Maybe but you have to imagine that each set stands for a number, and that operations between two numbers like x\_1 + x\_2 or x\_1 x\_2 are replaced by s\_1 \cup s\_2. Now imagine that you plug those set-numbers inside a neural network. What I want to know is the sets that you get at the very end, which track the dependencies of the output numbers on the input numbers. Making the sets disjoint at each layer, for each dimension, would be a waste of time

[Previous page](https://discourse.julialang.org/t/best-data-structure-for-fast-unions-of-large-sets-of-integers/113785.md?page=2)