# Find position on list (fast)

**URL:** <https://discourse.julialang.org/t/find-position-on-list-fast/71911>\
**Category:** General Usage\
**Created:** [November 22, 2021, 7:38pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911 "2021-11-22T19:38:56Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![programista](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/programista/32/5372_2.png) [@programista](https://discourse.julialang.org/u/programista)\
**Post date:** [November 22, 2021, 7:38pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/1 "2021-11-22T19:38:56Z")

</div>

Me vectors are very long and I am looking for efficient way to :  
If  
x=[“a”;“b”;“c”;“d”;“e”]  
and  
y=[“b”; “a”; “a”; “c”]

How to find , but very fast, position any y on x  
expected result:

2  
1  
1  
3

Thanks Pauls

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [November 22, 2021, 8:00pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/2 "2021-11-22T20:00:58Z")

</div>

Well, very fast is relative. The straightforward solution isn’t shabby 🙂

```julia
julia> using BenchmarkTools

julia> f1(x,y) = [findfirst(isequal(el), x) for el in y]
f1 (generic function with 1 method)

julia> @btime f1($x,$y);
  108.864 ns (1 allocation: 96 bytes)

```

Depending on how much you (over-)simplified your MWE, you could even use `Char`s instead of `String`s to get a free speedup 🙂

```julia
julia> xc = collect('a':'e');

julia> yc = ['b', 'a','a', 'c'];

julia> @btime f1($xc,$yc);
  71.986 ns (1 allocation: 96 bytes)

```

BTW, a similar alternative is

```julia
julia> f2(x,y) = [searchsortedfirst(x, el) for el in y]
f2 (generic function with 1 method)

julia> @btime f2($x,$y);
  146.619 ns (1 allocation: 96 bytes)

julia> @btime f2($xc,$yc);
  71.476 ns (1 allocation: 96 bytes)

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 22, 2021, 8:18pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/3 "2021-11-22T20:18:34Z")

</div>

In case the MWE is oversimplified and the vectors are really big, I found a [q&a](https://stackoverflow.com/questions/497338/efficient-list-intersection-algorithm) on [stackoverflow.com](http://stackoverflow.com). And then there is certainly more of [this](https://cstheory.stackexchange.com/questions/12357/most-efficient-algorithm-to-compute-set-difference).

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [November 22, 2021, 8:52pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/4 "2021-11-22T20:52:06Z")

</div>

If `x` is very large it will be more efficient to create a `Dict` mapping each element of `x` to its index.

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [November 22, 2021, 9:11pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/5 "2021-11-22T21:11:55Z")

</div>

Just to demonstrate @cjdoris’s great point:

```julia
julia> x = string.(Char.(1:1000));

julia> d = Dict(zip(x,1:length(x)));

julia> @btime f1($x,$y);
  2.621 μs (1 allocation: 96 bytes)

julia> f3(d,y) = [d[el] for el in y]
f3 (generic function with 1 method)

julia> @btime f3($d,$y);
  170.077 ns (1 allocation: 96 bytes)

```

Constant lookup is awesome 🙂

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [November 22, 2021, 9:16pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/6 "2021-11-22T21:16:49Z")

</div>

Remember that Julia has a built-in function for that, it is called `indexin`:

```julia
julia> x = ["a", "b", "c", "d", "e"]
5-element Vector{String}:
 "a"
 "b"
 "c"
 "d"
 "e"

julia> y = ["b", "a", "a", "c"]
4-element Vector{String}:
 "b"
 "a"
 "a"
 "c"

julia> indexin(y, x)
4-element Vector{Union{Nothing, Int64}}:
 2
 1
 1
 3

```

It may not be the fastest, but clean and easy to use.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [November 22, 2021, 9:17pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/7 "2021-11-22T21:17:21Z")

</div>

If it’s not the fastest, file an issue (or make a PR). It should be.

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [November 22, 2021, 9:20pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/8 "2021-11-22T21:20:54Z")

</div>

How could I forget about it 🙂 For comparison with the other variants (on my machine):

```julia
julia> f4(x,y) = indexin(y, x)
f4 (generic function with 1 method)

julia> @btime f4($x,$y);
  491.732 ns (5 allocations: 624 bytes)

```

Definitely not the fastest!

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [November 22, 2021, 9:28pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/9 "2021-11-22T21:28:41Z")

</div>

It does basically the same thing as `f3`. The big difference is that your timing of `f3` didn’t include the time to make the dictionary. (also the way `indexin` creates the dictionary isn’t especially efficient).

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [November 22, 2021, 9:36pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/10 "2021-11-22T21:36:36Z")

</div>

Fair enough. So it’s prioritizing the case of a large haystack. Would it perhaps make sense to decide on a strategy based on the length of the latter, i.e. use a polyalgorithm? Or do we just accept it (and only optimize the dict creation im possible)?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [November 22, 2021, 9:40pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/11 "2021-11-22T21:40:00Z")

</div>

Probably worth a PR.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [November 22, 2021, 9:57pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/12 "2021-11-22T21:57:27Z")

</div>

FWIW, for the inputs:

```julia
x = string.(Char.(1:1000))
y = string.(rand(Char.(1:1000), 500))

```

@carstenbauer’s `f3(x,y)`, with the dictionary built-in, takes about 2/3 of the time of Base’s `indexin(x,y)`

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 22, 2021, 11:20pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/13 "2021-11-22T23:20:41Z")

</div>

If these are operations on big arrays and performance matters, you should really think about changing to a data structure that supports more efficient searching. Otherwise you are stuck with O(length(x)×length(y)) complexity. Like:

> [@cjdoris](#):
>
> If `x` is very large it will be more efficient to create a `Dict` mapping each element of `x` to its index.

But ideally you should _start_ with a data structure that supports the operations you want quickly, rather than starting with some other data structure and then converting (or constructing auxiliary dictionaries).

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 22, 2021, 11:24pm UTC](https://discourse.julialang.org/t/find-position-on-list-fast/71911/14 "2021-11-22T23:24:11Z")

</div>

> [@carstenbauer](#):
>
> How could I forget about it 🙂 For comparison with the other variants (on my machine):
> 
> ```julia
> julia> f4(x,y) = indexin(y, x)
> f4 (generic function with 1 method)
> 
> julia> @btime f4($x,$y);
> 491.732 ns (5 allocations: 624 bytes)
> 
> ```
> 
> Definitely not the fastest!

Not a fair comparison, because the `indexin` function creates a dictionary mapping elements to indices, so when you apply `@btime` to `indexin` you are including the time to create the dictionary. In contrast, in your `f3` benchmark you did _not_ include the time to construct the `Dict`.

(Note also that `indexin` returns an array of `Union{Nothing,Int}` since it allows for the possibility that an element is missing from `x`, whereas your `f3` code threw an error in this case, and hence didn’t have to pay the price of a type-unstable array.)