# Performance tips for a function which finds n maximums in a matrix
**URL:** https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425
**Category:** Performance
**Tags:** performance, sortperm, speed-optimization, matrix
**Created:** [March 22, 2023, 12:19am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425 "2023-03-22T00:19:59Z")
**Posts on this page:** 9
**Page:** 1
### Author:  [@eduardosalaz](https://discourse.julialang.org/u/eduardosalaz)
#### Post date: [March 22, 2023, 12:19am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/1 "2023-03-22T00:19:59Z")
Hi everyone,
I have been trying to squeeze out as much performance as possible out from the following function, which finds the n largest (or maximum) values of a matrix and returns those values and their positions in the matrix, however I do have to note that in the specific case in which I am calling the function I really don’t need the values, just the indices:
```julia
function maximums(matrix, n)::Tuple{Vector{Int64}, Vector{CartesianIndex{2}}}
type = eltype(matrix)
vals = zeros(type, n)
indices = Array{Int64}(undef,n)
arr = Array{Tuple{type,CartesianIndex}}(undef, n)
@inbounds for i ∈ axes(matrix, 1), j ∈ axes(matrix, 2)
smallest, index = findmin(vals)
if matrix[i, j] > smallest
arr[index] = matrix[i, j], CartesianIndex(i, j)
vals[index] = matrix[i, j]
end
end
arr = sort(arr, by=x -> x[1], rev=true)
vals = [x[1] for x in arr]
indices = [x[2] for x in arr]
return vals, indices
end
```
I have already profiled it using @code\_warntype and pprof and I can’t seem to find any possible room for improvement. What can I do to make it run faster? Or does my logic need a rewrite from the ground up?
I call this function thousands of times in my main function so I would really appreciate any speed up.
Thank you very much!
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 22, 2023, 1:03am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/2 "2023-03-22T01:03:21Z")
You can make this thousands of times faster (look at `partialsort` and `partialsortperm`)
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 22, 2023, 1:19am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/3 "2023-03-22T01:19:16Z")
Specifically:
```julia
function maximums2(M, n)
v = vec(M)
l = length(v)
perm = partialsortperm(v, (l-n+1):l)
vals = v[perm]
indices = CartesianIndices(M)[perm]
return vals, indices
end
M = rand(Int, 1000,1000);
@time maximums(M, 10000);
8.694805 seconds (421.12 k allocations: 7.938 MiB)
@time maximums2(M, 10000);
0.010756 seconds (13 allocations: 15.488 MiB)
```
Specifically if `l` is the number of elements in the matrix, `maximums` is `O(l*n)` while `maximums2` is `O(l*log(n) + n)`
---
### Author:  [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)
#### Post date: [March 22, 2023, 5:45am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/4 "2023-03-22T05:45:30Z")
Or you adapt this one to get the maxima instead of minima, which is very efficient for small n.
> [@Find n smallest values in an n dims array](https://discourse.julialang.org/t/find-n-smallest-values-in-an-n-dims-array/81092/13):
>
> I think this version is not optimal if n is very small compared to the size of the array since you make a full sort and just retain a few smallest values. At the limit, imagine to get the lowest value of an array you make a sort first. That does not sound right. A dirty write-up like the following using BenchmarkTools A=rand(100,100,10,40,10); function arg\_n\_smallest\_values(A::AbstractArray{T,N}, n::Integer) where {T,N} perm = sortperm(vec(A)) ci = CartesianIndices(A) …
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [March 22, 2023, 6:02am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/5 "2023-03-22T06:02:56Z")
We can make this even faster for multiple calls by using the in-place version `partialsortperm!`
---
### Author:  [@DNF](https://discourse.julialang.org/u/DNF)
#### Post date: [March 22, 2023, 8:21am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/6 "2023-03-22T08:21:32Z")
> [@eduardosalaz](#):
>
> I can’t seem to find any possible room for improvement.
Using a better algorithm is of course the best choice, but if you just wanted to tweak your original code, then simply moving the line
> [@eduardosalaz](#):
>
> ```julia
> smallest, index = findmin(vals) # <-- this line
> if matrix[i, j] > smallest
> arr[index] = matrix[i, j], CartesianIndex(i, j)
> vals[index] = matrix[i, j]
> end
>
> ```
```julia
if matrix[i, j] > smallest
smallest, index = findmin(vals) # <-- move it here
arr[index] = matrix[i, j], CartesianIndex(i, j)
vals[index] = matrix[i, j]
end
```
is already a significant speedup. You need to initialize `smallest` and `index` outside the main loop, btw.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [March 22, 2023, 9:45am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/7 "2023-03-22T09:45:52Z")
```julia
using DataStructures
function Nlargest(v,N)
maxn = heapify!(tuple.(v[1:N],1:N))
maxn1=maxn[1]
for i in N+1:length(v)
e=(v[i],i)
if maxn1[1] < e[1]
heappop!(maxn)
heappush!(maxn,e)
maxn1=maxn[1]
end
end
#sort!(maxn,rev=true)
maxn
end
```
---
### Author:  [@eduardosalaz](https://discourse.julialang.org/u/eduardosalaz)
#### Post date: [March 23, 2023, 3:48am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/8 "2023-03-23T03:48:14Z")
Thank you everyone, here is my final working code:
```julia
function maximums2(M, n)
v = vec(M)
l = length(v)
ix = [1:l;]
partialsortperm!(ix, v, (l-n+1):l, initialized=true)
vals = v[ix[(l-n+1):l]]
indices = CartesianIndices(M)[ix[(l-n+1):l]]
return vals, indices
end
```
---
### Author:  [@DNF](https://discourse.julialang.org/u/DNF)
#### Post date: [March 23, 2023, 5:49am UTC](https://discourse.julialang.org/t/performance-tips-for-a-function-which-finds-n-maximums-in-a-matrix/96425/9 "2023-03-23T05:49:13Z")
> [@eduardosalaz](#):
>
> ```julia
> vals = v[ix[(l-n+1):l]]
> indices = CartesianIndices(M)[ix[(l-n+1):l]]
>
> ```
A micro-optimization: don’t slice `ix` twice, thst creates and allocates two arrays. Just do it once. (Maybe even use a view?)