# Replacing components with indices
**URL:** https://discourse.julialang.org/t/replacing-components-with-indices/113412
**Category:** Performance
**Tags:** indexing, dictionary, arrays, for-loop, map
**Created:** [April 24, 2024, 12:39am UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412 "2024-04-24T00:39:43Z")
**Posts on this page:** 13
**Page:** 1
### Author:  [@KeepLearning](https://discourse.julialang.org/u/KeepLearning)
#### Post date: [April 24, 2024, 12:39am UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/1 "2024-04-24T00:39:43Z")
I am wondering if the following can be done in a better way (without for loop, perhaps): given a vector and a vector of vectors, e.g.
```julia
v = [1, 2, 3, 3, 4, 4, 5]
u = [[1,2], [3, 5], [4]]
```
I like to get
```julia
[1, 1, 2, 2, 3, 3, 2]
```
by mapping the components in `v` to the indices of `u`. I came up with two ways as follows:
```julia
for i in eachindex(u)
v[findall(x -> x in u[i], v)] .= i
end
```
and
```julia
cond = Iterators.flatmap(enumerate(u) |> collect) do (i, x) map(reverse, i .=> x) end
for c in cond
replace!(v, c)
end
```
The reason why I have a question is that I wonder whether I could do somthing like
```julia
for i in eachindex(u)
replace!(v, u[i] .=> i)
end
```
, since `replace(v, 1=>0)` (for example) is possible and I thought of some extension and a possibility of avoiding using a for loop.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [April 24, 2024, 12:51am UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/2 "2024-04-24T00:51:54Z")
> [@KeepLearning](#):
>
> I am wondering if the following can be done in a better way (without for loop, perhaps):
I would worry less about getting rid of loops (which are perfectly fine in Julia) and more about making your complexity better. Right now, your computational cost scales proportionally to `length(v) * sum(length, u)`, which is pretty bad if the vectors are long. You can do _much_ better.
For example, make a single pass over `u` first to make a dictionary mapping values to indices:
```julia
d = Dict{eltype(eltype(u)),Int}()
for i in eachindex(u), x in u[i]
d[x] = i
end
```
then you can just do
```julia
julia> v .= get.(Ref(d), v, v)
7-element Vector{Int64}:
1
1
2
2
3
3
2
```
which has nearly linear complexity in the two lengths. You might also want to consider using the dictionary (or similar) in the first place to store your mapping (so that you never create `u` at all).
(And you can do even better if you have more knowledge of `u`. e.g. if you know that the elements of `u` cover all of the values of `v`, and that these are small integers β as in your example above β then you can just store an array mapping values to indices, rather than a dictionary.)
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [April 24, 2024, 4:52am UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/3 "2024-04-24T04:52:54Z")
Another option:
```julia
foldl((r,(i,e)) -> (r[e] .= i; r), pairs(u); init=fill(0,5))[v]
```
This option uses the fact `u` is a partition of the values of `v`, and the size `5` of the value set of `v` is encoded in the initialization. But it feels this knowledge is implicit in the OP setup.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [April 24, 2024, 9:44pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/4 "2024-04-24T21:44:26Z")
```julia
in.(v, permutedims(u))*axes(u,1)
```
---
### Author:  [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)
#### Post date: [April 24, 2024, 10:26pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/5 "2024-04-24T22:26:14Z")
Shorter:
`in.(v,u') * axes(u,1)`
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [April 24, 2024, 11:27pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/6 "2024-04-24T23:27:15Z")
> [@rafael.guerra](#):
>
> `in.(v,u') * axes(u,1)`
This is cute, but still has poor time complexity proportional to `length(v) * sum(length, u)`, as well as poor space complexity due to allocating a temporary matrix of size `length(v) * length(u)`.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [April 25, 2024, 7:25am UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/7 "2024-04-25T07:25:16Z")
```julia
indexinin(v,u)=[findfirst(eu->in(e, eu), u) for e in v]
```
this variant seems to be a little more efficient
```julia
function indexinin!(v,u)
for i in eachindex(v)
v[i]=findfirst(eu->in(v[i], eu), u)
end
end
```
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [April 25, 2024, 12:21pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/8 "2024-04-25T12:21:23Z")
> [@KeepLearning](#):
>
> The reason why I have a question is that I wonder whether I could do somthing like
>
> ```julia
> for i in eachindex(u)
> replace!(v, u[i] .=> i)
> end
>
> ```
>
> , since `replace(v, 1=>0)` (for example) is possible and I thought of some extension and a possibility of avoiding using a for loop.
Such a strategy would have the problem that the changes you apply can also change the part of the vector that has already been modified.
Unless you use kwarg count=1 π
```julia
foreach(e->replace!(v, e=>findfirst(eu->in(e, eu), u),count=1),v)
```
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [April 25, 2024, 12:55pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/9 "2024-04-25T12:55:47Z")
> [@rocco\_sprmnt21](#):
>
> this variant seems to be a little more efficient
It still has poor time complexity proportional to `length(v) * sum(length, u)`.
> [@rocco\_sprmnt21](#):
>
> `foreach(e->replace!(v, e=>findfirst(eu->in(e, eu), u),count=1),v)`
Also has the same poor time complexity.
Realize that nearly all of the solutions posted so far (excluding mine) correspond to three nested loops, hence the multiplicative complexity. Squeezing the code into a minimal number of library calls is fine if you want to minimize code size, but itβs too easy to fall into the myth of βlibrary calls = fastβ, or to think only about code size and not about [computational complexity](https://en.wikipedia.org/wiki/Computational_complexity).
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [April 25, 2024, 1:18pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/10 "2024-04-25T13:18:17Z")
In general terms I would say yes.
In my experience (I often try to independently create scripts that replace/improve library calls) and with my level of knowledge, library calls work better.
But I wonder if in the specific case, being u something like a partition of unique[v], the evaluation of the spatial or temporal complexity is not different from the general worst case.
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [April 25, 2024, 1:26pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/11 "2024-04-25T13:26:38Z")
> [@stevengj](#):
>
> Realize that nearly all of the solutions posted so far (excluding mine) correspond to three nested loops,
Hopefully, the βnearlyβ refers to my solution too. Which has the same low complexity. In fact, due to implementation of Dicts, assuming, as it seems, that `u` is a partition of `1:n` (n=5 here), my solution would keep a multlipicative advantage in larger scales (both in memory and speed). stevengj already mentions this possibility at the end of his solution, so perhaps Iβve added nothing novel.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [April 25, 2024, 1:44pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/12 "2024-04-25T13:44:40Z")
I wanted to compare this with the script that uses findfirst, but I canβt measure it with @benchmark f(β¦) setup=(β¦)
```julia
function richcomplexity!(u,vv)
d=zeros(Int, length(unique(vv)))
for i in eachindex(u), x in u[i]
d[x] = i
end
vv .= getindex.(Ref(d), vv)
end
```
I tried with larger vectors than the ones provided in the OP.
```julia
bigv=rand(1:100, 10^3)
uu=unique(bigv)
p=sort(rand(uu),10))
pl=[1;p]
pr=[p.-1;length(uu)
bigu=getindex.([uu], (:).(pl,pr))
```
```julia
ulia> function richcomplexity(u,v)
d = Dict{eltype(eltype(u)),Int}()
for i in eachindex(u), x in u[i]
d[x] = i
end
v .= get.(Ref(d), v, v)
end
richcomplexity (generic function with 1 method)
julia> @benchmark richcomplexity($bigu,cv) setup=(cv=copy($bigv))
BenchmarkTools.Trial: 10000 samples with 6 evaluations.
Range (min β¦ max): 4.833 ΞΌs β¦ 870.450 ΞΌs β GC (min β¦ max): 0.00% β¦ 98.16%
Time (median): 5.400 ΞΌs β GC (median): 0.00%
Time (mean Β± Ο): 8.108 ΞΌs Β± 24.920 ΞΌs β GC (mean Β± Ο): 8.84% Β± 2.96%
βββ
ββββββββ βββ β
βββββββββββββββββββββββββββββββββββββββ
β
β
β
βββ
β
ββββββ
β
β
βββ
ββ β
4.83 ΞΌs Histogram: log(frequency) by time 31.8 ΞΌs <
Memory estimate: 6.36 KiB, allocs estimate: 10.
julia> function indexinin!(v,u)
for i in eachindex(v)
v[i]=findfirst(eu->in(v[i], eu), u)
end
end
indexinin! (generic function with 1 method)
julia> @benchmark indexinin!(cv,$bigu) setup=(cv=copy($bigv))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
Range (min β¦ max): 28.000 ΞΌs β¦ 1.277 ms β GC (min β¦ max): 0.00% β¦ 0.00%
Time (median): 29.800 ΞΌs β GC (median): 0.00%
Time (mean Β± Ο): 32.776 ΞΌs Β± 20.407 ΞΌs β GC (mean Β± Ο): 0.00% Β± 0.00%
ββββββ β β
ββ βββββββ β
βββββββββββββββββββββββββββββββββ
βββββββββββββββββββββ
βββββ β
28 ΞΌs Histogram: log(frequency) by time 78 ΞΌs <
Memory estimate: 0 bytes, allocs estimate: 0.
```
It seems like @stevenj said
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [April 25, 2024, 4:00pm UTC](https://discourse.julialang.org/t/replacing-components-with-indices/113412/13 "2024-04-25T16:00:55Z")
> [@rocco\_sprmnt21](#):
>
> In my experience (I often try to independently create scripts that replace/improve library calls) and with my level of knowledge, library calls work better.
βLibrary calls are fasterβ is an unreliable heuristic.
1. First, you should always try to have some sense of what the library calls are doing β at least know the expected complexity. (e.g. `findfirst(predicate, array)` or `x in array` are both sequential search, so have an average cost that scales with the array length multiplied by the cost of the predicate).
2. Second, as I [wrote in another blog post](https://julialang.org/blog/2017/01/moredots/#why_vectorized_code_is_not_as_fast_as_it_could_be): _There is a tension between two general principles in computing: on the one hand, **re-using** highly optimized code is good for performance; on the other other hand, optimized code that is **specialized** for your problem can usually beat general-purpose functions._
That being said, there is absolutely nothing wrong with writing code to minimize code length or maximize clarity (hopefully both) rather than optimizing speed. But you should be _aware_ that you are doing so, _especially_ if your code has suboptimal _complexity/scaling_ (not just a suboptimal constant factor, which requires a lot more expertise to deal with).
> [@Dan](#):
>
> Hopefully, the βnearlyβ refers to my solution too.
Right, your solution also does one linear-time pass over `u` and one linear-time pass over `v`. π