comp_2.jl

using Base.Order
using Base.SparseMatrix.binarysearch

const N = 10^2
const NN = N*10^2
const rowvalA = sort(randperm(NN)[1:N]) 
const iss = randperm(NN) # disordered needle
const iso = [1:NN]       # ordered needles

function h1(rowvalA, iss)
    res::Int = 0
    print("bin      ")
    @time for i in iss
	res += binarysearch(rowvalA, i, 1, N)
    end
    res
end

function h2(rowvalA, iss)
    res = 0
    print("sort     ")
    @time for i in iss
	r = searchsorted(rowvalA, i, 1, N, Forward)
	j = isempty(r) ? -1 : r[1]
	res += j
    end
    res
end

function h3(rowvalA, iss)
    res = 0
    print("sortlast ")
    @time for i in iss
	r = searchsortedfirst(rowvalA, i, 1, N, Forward)
        j = ((r <= N) && (rowvalA[r[1]]==i)) ? r : -1
	res += j
    end
    res
end

res0 = h1(rowvalA, iss)
res1 = h2(rowvalA, iss)
res2 = h3(rowvalA, iss)
println("randperm(NN) input:")
res0 = h1(rowvalA, iss)
res1 = h2(rowvalA, iss)
res2 = h3(rowvalA, iss)
@assert res0==res1==res2

println(" ")

res0 = h1(rowvalA, iso)
res1 = h2(rowvalA, iso)
res2 = h3(rowvalA, iso)
println("[1:NN] input:")
res0 = h1(rowvalA, iso)
res1 = h2(rowvalA, iso)
res2 = h3(rowvalA, iso)

@assert res0==res1==res2

results

# second run only:

N=10, NN=1000                                                                                                                                                                                                                          randperm(NN) input:
bin      elapsed time: 2.8188e-5 seconds (0 bytes allocated)
sort     elapsed time: 3.2151e-5 seconds (0 bytes allocated)
sortlast elapsed time: 2.8448e-5 seconds (0 bytes allocated)
[1:NN] input:
bin      elapsed time: 2.0407e-5 seconds (0 bytes allocated)
sort     elapsed time: 2.2125e-5 seconds (0 bytes allocated)
sortlast elapsed time: 2.1341e-5 seconds (0 bytes allocated)

N=100, NN=10000
randperm(NN) input:
bin      elapsed time: 0.00022216 seconds (0 bytes allocated)
sort     elapsed time: 0.000368998 seconds (0 bytes allocated)
sortlast elapsed time: 0.000235602 seconds (0 bytes allocated)
[1:NN] input:
bin      elapsed time: 0.000182682 seconds (0 bytes allocated)
sort     elapsed time: 0.000149129 seconds (0 bytes allocated)
sortlast elapsed time: 0.000188118 seconds (0 bytes allocated)

N=1000, NN=100000
randperm(NN) input:
bin      elapsed time: 0.002756478 seconds (0 bytes allocated)
sort     elapsed time: 0.005649829 seconds (0 bytes allocated)
sortlast elapsed time: 0.003916286 seconds (0 bytes allocated)
[1:NN] input:
bin      elapsed time: 0.002726484 seconds (0 bytes allocated)
sort     elapsed time: 0.001809206 seconds (0 bytes allocated)
sortlast elapsed time: 0.00395091 seconds (0 bytes allocated)

N=10_000, NN=1000000
randperm(NN) input:
bin      elapsed time: 0.046143891 seconds (0 bytes allocated)
sort     elapsed time: 0.070356426 seconds (0 bytes allocated)
sortlast elapsed time: 0.047735628 seconds (0 bytes allocated)
[1:NN] input:
bin      elapsed time: 0.037985047 seconds (0 bytes allocated)
sort     elapsed time: 0.022259275 seconds (0 bytes allocated)
sortlast elapsed time: 0.038493442 seconds (0 bytes allocated)

N=100_000, NN=10000000
randperm(NN) input:
bin      elapsed time: 0.788107059 seconds (0 bytes allocated)
sort     elapsed time: 1.000017152 seconds (0 bytes allocated)
sortlast elapsed time: 0.801757287 seconds (0 bytes allocated)
[1:NN] input:
bin      elapsed time: 0.482200701 seconds (0 bytes allocated)
sort     elapsed time: 0.262308346 seconds (0 bytes allocated)
sortlast elapsed time: 0.488023373 seconds (0 bytes allocated)

N=1_000_000, NN=100000000
randperm(NN) input:
bin      elapsed time: 21.122378384 seconds (0 bytes allocated)
sort     elapsed time: 18.886542263 seconds (0 bytes allocated)
sortlast elapsed time: 22.181968227 seconds (0 bytes allocated)
 [1:NN] input:
bin      elapsed time: 5.899968547 seconds (0 bytes allocated)
sort     elapsed time: 3.073599917 seconds (0 bytes allocated)
sortlast elapsed time: 6.253600095 seconds (0 bytes allocated)