# True power set of a set is slower than power array of array

**URL:** <https://discourse.julialang.org/t/true-power-set-of-a-set-is-slower-than-power-array-of-array/59464>\
**Category:** Performance\
**Created:** [April 17, 2021, 6:08am UTC](https://discourse.julialang.org/t/true-power-set-of-a-set-is-slower-than-power-array-of-array/59464 "2021-04-17T06:08:57Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Wei\_Yang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/wei_yang/32/23951_2.png) [@Wei\_Yang](https://discourse.julialang.org/u/Wei_Yang)\
**Post date:** [April 17, 2021, 6:08am UTC](https://discourse.julialang.org/t/true-power-set-of-a-set-is-slower-than-power-array-of-array/59464/1 "2021-04-17T06:08:57Z")

</div>

I’m trying to create a power set function with only set operations, but it turns out to be much slower than the array version. I wonder why this is the case, and how to make the Set version as fast as the array version.

Thank you ! 🙂

 ![image](https://global.discourse-cdn.com/julialang/original/3X/c/7/c7c92e97dee1b8b2327ec7ee1be9d8b788e57be8.png)

```
function powerset(x::AbstractArray)   
    result = [[]]
    for elem in x, j in eachindex(result)
        push!(result, [result[j] ; elem])
    end
    result
end

```

@time powerset([1:17…]);

```
function powerset(x::AbstractSet)   
    result = Set([Set()])
    for elem in x, j in result
        union!(result, Set([union(j,elem)]))
    end
    result
end

```

@time powerset(Set(1:17));

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [April 17, 2021, 8:50am UTC](https://discourse.julialang.org/t/true-power-set-of-a-set-is-slower-than-power-array-of-array/59464/2 "2021-04-17T08:50:10Z")

</div>

You can [profile](https://docs.julialang.org/en/v1/manual/profile/) it to see what’s slow. Before looking at the code, I would guess that set union is slower than array concatenation because set union also requires checking for duplicates.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [April 17, 2021, 3:48pm UTC](https://discourse.julialang.org/t/true-power-set-of-a-set-is-slower-than-power-array-of-array/59464/4 "2021-04-17T15:48:09Z")

</div>

The expensive part is not actually checking for duplicates, but because `Set` is implemented as a hashmap, each insertion into a set needs to calculate the hash of the item first. Hashing a set is currently `O(n)`, since the overall hash depends on each element of the set. OTOH, appending to an array is amortized to only be `O(log(n))`. I wonder whether we can use a similar strategy for hashing sets as we do for arrays, where for large arrays we only actually sample `O(log(n))` items. That might be worth opening an issue actually.

---

<div class="post-metadata">

**Author:** ![Wei\_Yang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/wei_yang/32/23951_2.png) [@Wei\_Yang](https://discourse.julialang.org/u/Wei_Yang)\
**Post date:** [April 17, 2021, 4:34pm UTC](https://discourse.julialang.org/t/true-power-set-of-a-set-is-slower-than-power-array-of-array/59464/5 "2021-04-17T16:34:49Z")

</div>

Wow, thank you for letting me know `profile`. Looking at the output, there certainly seems to be alot more things going on in the Set version.

A total of 11 snapshots for `powerset([1:15...])` while 471 for `powerset(Set(1:15))`