# Fast ways to check if an element is in a vector of vector of elements

**URL:** <https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598>\
**Category:** Performance\
**Tags:** question\
**Created:** [October 22, 2024, 3:29pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598 "2024-10-22T15:29:41Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![rakshith95](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rakshith95/32/44606_2.png) [@rakshith95](https://discourse.julialang.org/u/rakshith95)\
**Post date:** [October 22, 2024, 3:29pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/1 "2024-10-22T15:29:41Z")

</div>

Hello ,  
What would be the most efficient way to look for a number in a vector of vector of numbers?  
i.e.  
Data: t = [[1,2,3] , [4,5,6] , [1,10,12], [1,4,5] ]  
Input: 1  
Output: 1,3,4

I could do something like `findall(map(x->1 in x, t))` but this is quite slow, and I’m pretty sure it’s not the best way to do this.  
Thanks!

---

<div class="post-metadata">

**Author:** ![Tomas\_Pevny](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomas_pevny/32/25466_2.png) [@Tomas\_Pevny](https://discourse.julialang.org/u/Tomas_Pevny)\
**Post date:** [October 22, 2024, 3:43pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/2 "2024-10-22T15:43:46Z")

</div>

Make it a set, or give it some ordering.

---

<div class="post-metadata">

**Author:** ![rakshith95](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rakshith95/32/44606_2.png) [@rakshith95](https://discourse.julialang.org/u/rakshith95)\
**Post date:** [October 22, 2024, 4:31pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/3 "2024-10-22T16:31:48Z")

</div>

Thanks, but could you also please tell me how this would help?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 22, 2024, 4:56pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/4 "2024-10-22T16:56:29Z")

</div>

```julia
findall(v->in(1, v), t)

```

or

```julia
findall(1 in v for v in t)

```

---

<div class="post-metadata">

**Author:** ![zweiglimmergneis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zweiglimmergneis/32/7892_2.png) [@zweiglimmergneis](https://discourse.julialang.org/u/zweiglimmergneis)\
**Post date:** [October 22, 2024, 5:01pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/5 "2024-10-22T17:01:37Z")

</div>

I’m interested in an answer, too.  
The following didn’t speed up the searching:

```julia
t_set = map(Set, t)
ix = findall(map(x->1 in x, t_set))

```

neither

```julia
t_sort = map(sort, t)
function fsn_loop(v, n)
    # assume that the elements in v are sorted
    hits = Int[]
    for (i, v_l) in enumerate(v)
        determined = false        
        for v_ll in v_l
            if v_ll == n
                push!(hits, i)
                determined = true
                break
            end
            if v_ll > n
                determined = true
                break
            end
        end
        if determined
            continue
        end
    end
    return hits    
end
ix = fsn_loop(t_sort, 1) 

```

For `t` having 1e5 elements, `@btime` gives around 1 ms, as does DNF’s solution.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 22, 2024, 5:05pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/6 "2024-10-22T17:05:56Z")

</div>

My previous experience tells me that this should be the fastest:

> [@DNF](#):
>
> ```julia
> findall(v->in(1, v), t)
> 
> ```

But I must say I have seen a number of strange performance issues in v1.11, and now it benchmarks as slower than `findall(map(x->1 in x, t))`, which, frankly, makes no sense to me, since the latter creates a redundant temporary array and also passes twice over memory 🤷‍♂️

---

<div class="post-metadata">

**Author:** ![rakshith95](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rakshith95/32/44606_2.png) [@rakshith95](https://discourse.julialang.org/u/rakshith95)\
**Post date:** [October 22, 2024, 5:42pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/7 "2024-10-22T17:42:03Z")

</div>

Hm, okay, thank you!

> since the latter creates a redundant temporary array and also passes twice over memory 🤷‍♂️

I thought there would be a better way, but I guess I’m better off sticking to `findall(map(x->1 in x, t))` for now in that case.

---

<div class="post-metadata">

**Author:** ![Tomas\_Pevny](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomas_pevny/32/25466_2.png) [@Tomas\_Pevny](https://discourse.julialang.org/u/Tomas_Pevny)\
**Post date:** [October 22, 2024, 7:19pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/8 "2024-10-22T19:19:17Z")

</div>

So I have not understood the problem first. I think the big question is, how frequently you want to run this search. If once, the answer by @DNF is OK. if multiple times, you should build the index. Like

```julia
a = [[1,2,3],[4,5,6],[1,5,6]]
index = Dict{Int,Vector{Int}}()
for (i, jj) in enumerate(a)
       for j in jj
       push!(get!(index, j, Int[]), i)
       end
 end

julia> index[1]
2-element Vector{Int64}:
 1
 3
```

---

<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:** [October 22, 2024, 7:56pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/9 "2024-10-22T19:56:24Z")

</div>

I would give this version a chance too

```julia
function find1s(a)
    r=Int64[]
    for i in eachindex(a)
    if !isnothing(findfirst(==(1),a[i]))
        push!(r,i)
    end
    end
    r
end

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 22, 2024, 8:32pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/10 "2024-10-22T20:32:46Z")

</div>

My package SmallCollections.jl contains a vectorized version of `in` for suitable types (not yet in the published version).

EDIT: It’s also vectorized for `SVector` in StaticArrays.jl.

This might speed things up if the element vectors are “small” (say, up to 32 or 64 elements). For example, for

```julia
using SmallCollections, Chairmarks
using Base: Fix1

T = Int32
N = 3
t = [rand(T, N) for _ in 1:1_000_000]
x = T(1)

```

I get

```julia
julia> @b t findall(Fix1(in, $x), _) # analogous to OP
5.546 ms (5 allocs: 122.250 KiB)

julia> @b map(FixedVector{N}, t) findall(Fix1(in, $x), _)
881.295 μs (5 allocs: 122.250 KiB)

julia> @b map(SmallVector{N}, t) findall(Fix1(in, $x), _)
3.204 ms (5 allocs: 122.250 KiB)

```

`FixedVector{N,T}` is like `SVector{N,T}` from StaticArrays.jl. `SmallVector{N,T}` can hold up to `N` elements of type `T`.

To try it out, you can install the relevant branch via

```julia
pkg> add https://github.com/matthias314/SmallCollections.jl#fixedvector

```

EDIT: fast `in` for `SmallVector` is now implemented.

---

<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:** [October 22, 2024, 9:11pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/11 "2024-10-22T21:11:14Z")

</div>

could you check this ?

```julia
function f1(a,e)
    r=Vector{Int}(undef,length(a))
    j=0
    for i in eachindex(a)
          !isnothing(findfirst(==(e),a[i])) && (r[j+=1]=i)
    end
    resize!(r,j) 
end

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 22, 2024, 9:18pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/12 "2024-10-22T21:18:38Z")

</div>

> [@rocco\_sprmnt21](#):
>
> could you check this ?

Was this for me? I get (with the same `t` and `x` as before)

```julia
julia> @b t f1(_, $x)
4.813 ms (3 allocs: 7.629 MiB)

julia> @b map(FixedVector{N}, t) f1(_, $x)
2.299 ms (3 allocs: 7.629 MiB)

```

---

<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:** [October 22, 2024, 9:23pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/13 "2024-10-22T21:23:29Z")

</div>

> [@matthias314](#):
>
> Was this for me? I get (with the same `t` and `x` as before)

Sorry.  
Yes is for you.  
I meant to do the proof by redefining the vector of vectors in the following way

```julia
T = Int32
N = 3
t = [T.(rand(1:10^5, N)) for _ in 1:1_000_000]
st=SArray{Tuple{N}}.(t)

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 22, 2024, 9:35pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/14 "2024-10-22T21:35:17Z")

</div>

Here it is:

```julia
julia> @b f1($st, $x)
1.717 ms (3 allocs: 7.629 MiB)

julia> @b map(FixedVector{N}, st) findall(Fix1(in, $x), _)
902.658 μs (6 allocs: 122.531 KiB)

```

---

<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:** [October 22, 2024, 9:46pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/15 "2024-10-22T21:46:42Z")

</div>

f1 using findfirst -assuming that there is only one value being searched for or that it is enough to find the first one- would become more effective for vectors a little longer than 3.  
Could you try for N=32?

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 22, 2024, 10:05pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/16 "2024-10-22T22:05:36Z")

</div>

As in previous post, just with `N = 32`:

```julia
julia> @b f1($st, $x)
14.917 ms (3 allocs: 7.629 MiB)

julia> @b map(FixedVector{N}, st) findall(Fix1(in, $x), _)
65.604 ms (7 allocs: 124.781 KiB)

julia> @b map(collect, st) findall(Fix1(in, $x), _)
26.547 ms (7 allocs: 124.781 KiB)

```

Now my version is much slower, even slower than `findall` with `Vector`. I don’t understand this because `in` is faster for `FixedVector`:

```julia
julia> w = st[1]; @b $x in $w
4.290 ns

julia> @b FixedVector{N}(w) $x in _
2.711 ns

julia> @b collect(w) $x in _
15.173 ns

```

Using `findfirst` looks slower:

```julia
julia> @b findfirst(==($x), $w) === nothing
13.547 ns

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 22, 2024, 10:21pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/17 "2024-10-22T22:21:58Z")

</div>

With `in` instead of `findfirst`, `f1` becomes even faster (`N = 32`):

```julia
julia> @b f1($st, $x)
15.493 ms (3 allocs: 7.629 MiB)

julia> @b f1_in($st, $x)
6.463 ms (3 allocs: 7.629 MiB)

julia> @b map(FixedVector{N}, st) f1_in(_, $x)
6.782 ms (3 allocs: 7.629 MiB)

```

where

```julia
function f1_in(a,e)
    r=Vector{Int}(undef,length(a))
    j=0
    for i in eachindex(a)
        if e in a[i] # !isnothing(findfirst(==(e),a[i]))
            r[j+=1]=i
        end
    end
    resize!(r,j) 
end

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 22, 2024, 10:44pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/18 "2024-10-22T22:44:01Z")

</div>

The problem seems to be `findall`. With `N = 32`, `T = Int32`, `x = T(1)` and

```julia
t = [T.(rand(1:10^5, N)) for _ in 1:1_000_000]
st = map(SVector{N}, t)

```

(as before), I get

```julia
julia> @b findall(Fix1(in, $x), $st)
68.203 ms (7 allocs: 124.781 KiB)

julia> @b [i for (i, w) in enumerate($st) if $x in w]
6.780 ms (7 allocs: 7.562 KiB)

```

EDIT: Also

```julia
julia> t2 = map(SmallVector{N}, t);
julia> @b [i for (i, w) in enumerate($t2) if $x in w]
7.595 ms (7 allocs: 7.562 KiB)

```

---

<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:** [October 23, 2024, 8:29am UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/19 "2024-10-23T08:29:59Z")

</div>

> [@matthias314](#):
>
> With `in` instead of `findfirst`

It seems that the implementation of some method of the function `in` is able to exploit the fact of having a static array better than `findfirst` can do.  
it would be interesting to have a documentation of functions like these that at first glance seem to do the same thing (at least from a (high?) ​​"logical" point of view), that explains what algorithm (algorithms?) they use in the various cases and when one can be “convenient” compared to the other.  
A curiosity of a similar kind comes to me from the fact that the use of enumerate that makes available both the index and the value of an array is slower than the following version where instead from time to time, having only the index, you have to obtain the value of the array element (in this case in turn an array).

```julia
julia> T = Int32
Int32

julia> N = 32
32

julia> t = [T.(rand(1:10^5, N)) for _ in 1:1_000_000];

julia> st=SArray{Tuple{N}}.(t);

julia> x=T(1)
1

julia> @b [i for (i, w) in enumerate($st) if $x in w]
16.229 ms (6 allocs: 7.609 KiB)

julia> @b [i for i in eachindex($st) if $x in $st[i]]
7.199 ms (6 allocs: 7.609 KiB)

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [October 23, 2024, 12:14pm UTC](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598/20 "2024-10-23T12:14:48Z")

</div>

> [@rocco\_sprmnt21](#):
>
> `in` is able to exploit the fact of having a static array better than `findfirst`

This is because the implementation of `in` for `SVector` can be vectorized while that of `findfirst` (the default method for `AbstractArray`) cannot. However, `findfirst` for `FixedVector` and `SmallVector` is vectorized (for suitable types), and in fact `in` for SmallVector is defined as

```julia
in(x, v::AbstractSmallVector) = findfirst(==(x), v) !== nothing

```

I don’t find it surprising that `enumerate` is slower than `eachindex`. With Julia 1.11.0, the difference is quite small on my machine:

```julia
julia> @b [i for (i, w) in enumerate($st) if $x in w]
6.792 ms (7 allocs: 7.562 KiB)

julia> @b [i for i in eachindex($st) if $x in $st[i]]
6.035 ms (7 allocs: 7.562 KiB)

```

[Next page](https://discourse.julialang.org/t/fast-ways-to-check-if-an-element-is-in-a-vector-of-vector-of-elements/121598.md?page=2)