# Fastest way to filter when right hand sinde of \`in\` is large

**URL:** https://discourse.julialang.org/t/fastest-way-to-filter-when-right-hand-sinde-of-in-is-large/52526
**Category:** Performance
**Created:** [December 28, 2020, 6:18pm UTC](https://discourse.julialang.org/t/fastest-way-to-filter-when-right-hand-sinde-of-in-is-large/52526 "2020-12-28T18:18:51Z")
**Posts on this page:** 4
**Page:** 1

<div class="post-metadata">

### Author: ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)
#### Post date: [December 28, 2020, 6:18pm UTC](https://discourse.julialang.org/t/fastest-way-to-filter-when-right-hand-sinde-of-in-is-large/52526/1 "2020-12-28T18:18:51Z")

</div>

I’m facing a problem where I would like to filter a dataset by using only those IDs that occur in another vector (that is around 100,000 elements long). If I just use `in` that takes forever as, I assume it checks every element in that vector. Is there a way to make this lookup faster similar to a `Dict`?

Small example

```julia
using Random, StatsBase
Random.seed!(42);
ids = [randstring(10) for _ in 1:100_000];
ids_use = sample(ids, 10_000, replace=false);

```

```julia
julia> @time filter(id -> id ∈ ids_use, ids)
  6.725424 seconds (10.95 k allocations: 1.281 MiB)

```

Thanks!

---

<div class="post-metadata">

### Author: ![lungben](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lungben/32/12314_2.png) [@lungben](https://discourse.julialang.org/u/lungben)
#### Post date: [December 28, 2020, 6:23pm UTC](https://discourse.julialang.org/t/fastest-way-to-filter-when-right-hand-sinde-of-in-is-large/52526/2 "2020-12-28T18:23:00Z")

</div>

Use a set instead of an array for the right hand side.  
Membership check in a set scales with O(1), whereas an array it scales with O(n).

---

<div class="post-metadata">

### Author: ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)
#### Post date: [December 28, 2020, 6:30pm UTC](https://discourse.julialang.org/t/fastest-way-to-filter-when-right-hand-sinde-of-in-is-large/52526/3 "2020-12-28T18:30:19Z")

</div>

Thank you this is the solution!

For completeness:

```julia
ids_set = Set(ids_use)

```

```julia
julia> @time filter(id -> id ∈ ids_set, ids)
  0.032714 seconds (10.95 k allocations: 1.282 MiB)

```

---

<div class="post-metadata">

### Author: ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)
#### Post date: [December 28, 2020, 6:48pm UTC](https://discourse.julialang.org/t/fastest-way-to-filter-when-right-hand-sinde-of-in-is-large/52526/4 "2020-12-28T18:48:41Z")

</div>

I also find the implementation of `Set` interesting

```julia
struct Set{T} <: AbstractSet{T}
    dict::Dict{T,Nothing}

    Set{T}() where {T} = new(Dict{T,Nothing}())
    Set{T}(s::Set{T}) where {T} = new(Dict{T,Nothing}(s.dict))
end

```

Explains why it is as fast as a `Dict` 😉