-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathcollision_benchmark.jl
109 lines (108 loc) · 4.96 KB
/
collision_benchmark.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
@show Threads.nthreads()
#Threads.nthreads() = 4
versioninfo()
# Julia Version 1.7.0
# Commit 3bf9d17731 (2021-11-30 12:12 UTC)
# Platform Info:
# OS: Linux (x86_64-pc-linux-gnu)
# CPU: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
# WORD_SIZE: 64
# LIBM: libopenlibm
# LLVM: libLLVM-12.0.1 (ORCJIT, skylake)
# Environment:
# JULIA_NUM_THREADS = 4
using Stuffing
import WordCloud
using Plots
unicodeplots()
using Random
# Random.seed!(8)
using BenchmarkTools
function getqtrees(objs, n)
sz = round(Int, 35*sqrt(n)) #The area of mask increases linearly
objs = Iterators.flatten((repeat(objs, n÷length(objs)), objs[1:n%length(objs)]))
mqt, qts... = qtrees(trues(sz, sz), objs)
@assert length(qts) == n
place!(mqt, qts)
return qts
end
B = []
N = []
objs = [WordCloud.rendertext(randstring(rand(1:8)), 6randexp()+8, border=1, angle=rand(-90:1:90)) for i in 1:5000];
for n in 1:50000
(n%10^floor(Int, log10(n)) == 0) || continue
display("="^10*"$n"*"="^10)
qts = getqtrees(objs, n)
b = @benchmark totalcollisions($qts)
push!(B, b.times)
push!(N, n)
T = mean.(B)/1000
p = plot(N, T, legend=nothing)
xaxis!("number")
yaxis!("time (μs)")
xlims!(0, N[end])
ylims!(0, maximum(T))
# title!(string(n))
display(p)
end
# ┌────────────────────────────────────────┐
# 1.6181e5 │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠊│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠊⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠔⠁⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠒⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# time (μs) │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠒⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠔⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# │⠀⠀⠀⠀⢀⣀⠖⠊⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# 0 │⣀⡠⠔⠒⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
# └────────────────────────────────────────┘
# ⠀0⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀number⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀50000⠀
display([n=>mean(b)/1000 for (n,b) in zip(N, B)])
# 41-element Vector{Pair{Int64, Float64}}:
# 1 => 0.030337110753768843
# 2 => 3.8218126875
# 3 => 5.4353064
# 4 => 7.285635033333333
# 5 => 7.506913866666666
# 6 => 7.1942441
# 7 => 7.449355683333331
# 8 => 7.4442965
# 9 => 8.0257573
# 10 => 9.063585866666667
# 20 => 18.6085887
# 30 => 27.1033925
# 40 => 33.74430890000001
# 50 => 45.8884247
# 60 => 53.154100299999996
# 70 => 61.5332195
# 80 => 67.950358
# 90 => 74.40709269999999
# 100 => 94.4142978
# 200 => 218.3041868
# 300 => 368.377914
# 400 => 545.2249844212836
# 500 => 655.0181617918314
# 600 => 750.8218311198309
# 700 => 937.2056202936747
# 800 => 1061.1064743234604
# 900 => 1204.9898514755685
# 1000 => 1303.2047123430962
# 2000 => 2909.305055393586
# 3000 => 4768.721655205349
# 4000 => 6774.760210312076
# 5000 => 8872.888227353464
# 6000 => 11512.653802298852
# 7000 => 13086.52932722513
# 8000 => 16251.792931818181
# 9000 => 18271.59549270073
# 10000 => 21244.32552966102
# 20000 => 52872.430073684205
# 30000 => 88738.72978947368
# 40000 => 125490.6995
# 50000 => 161809.58080645162