The quasi-best MaxN function

General Usage Performance
3

Thanks. Based on your indication I found this topic which seems to refer to the library function in question.

I tried to use it in order to obtain the first 5 largest values of a list and I made comparisons between different functions including one derived from that of the base library.

function MaxN4(cr,N)
    maxn=Int[]
    r=copy(cr)
    for x in 1:N
        p=popfirst!(r)
        for (i,e) in enumerate(r)
            if p < e
                r[i],p = p,e
            end
        end
        push!(maxn,p)
    end
    maxn
end

maxN2(s,N)= sort(s,rev=true)[1:N]

MaxNPS(r,N) = sort(r, alg=PartialQuickSort(N),rev=true)[1:N]

Below are the results obtained for the following two vectors

re7=rand(1:10^9, 10^7)

re6=rand(1:10^8, 10^6)

per re6:

using BenchmarkTools

@btime sort(re6,rev=true)[1:5]
# 67.170 ms (3 allocations: 7.63 MiB)
# 5-element Array{Int64,1}:
#  99999902
#  99999827
#  99999775
#  99999613
#  99999409
@btime MaxN4(re6,5)
# 5.630 ms (5 allocations: 7.63 MiB)
# 5-element Array{Int64,1}:
#  99999902
#  99999827
#  99999775
#  99999613
#  99999409

@btime MaxNPS(re6,5)
# 10.661 ms (4 allocations: 7.63 MiB)
# 5-element Array{Int64,1}:
#  99999902
#  99999827
#  99999775
#  99999613
#  99999409

per re7:


@btime sort(re7,rev=true)[1:5]
#   778.337 ms (3 allocations: 76.29 MiB)
# 5-element Array{Int64,1}:
#  999999837
#  999999762
#  999999473
#  999999470
#  999999383

@btime MaxN4(re7,5)
# 62.091 ms (5 allocations: 76.29 MiB)
# 5-element Array{Int64,1}:
#  999999837
#  999999762
#  999999473
#  999999470
#  999999383

@btime MaxNPS(re7,5)
# 79.725 ms (4 allocations: 76.29 MiB)
# 5-element Array{Int64,1}:
#  999999837
#  999999762
#  999999473
#  999999470
#  999999383

Given the results I have the doubt of not having done something properly either in the measurement or in the definition of the function that uses the library partialquicksort.