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
|
local geom = require 'geometry'
function progress(fraction)
local bar = string.rep('=', math.ceil(40*fraction))
io.write(string.format('[%-40s]\r', bar))
io.flush()
end
function benchmark(f, N)
local percent_no = math.floor(N / 100)
local start = os.time()
for i=1,100 do
progress(i/100)
for j=1,percent_no do
f()
end
end
print()
print(
string.format(
'function %s: %d seconds (%d iterations)',
tostring(f), os.difftime(os.time(), start), percent_no * 100
)
)
end
function random_point()
return geom.point(math.random(), math.random())
end
local n_points = 1e5
print(string.format('generating %d points...', n_points))
local tree = geom.quadtree()
local points = {}
for i=1,n_points do
progress(i/n_points)
local point = random_point()
table.insert(points, point)
tree:insert(point)
end
print()
local find_closest = function(point)
local dist = math.huge
local closest
for _, pt in ipairs(points) do
if point:distance_to(pt) < dist then
dist = point:distance_to(pt)
closest = pt
end
end
return closest
end
print('benchmarking brute-force')
benchmark(
function()
local point = random_point()
find_closest(point)
end, 10000)
print('benchmarking quadtree')
benchmark(
function()
local point = random_point()
tree:get_closest(point)
end, 10000)
|
