summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--city/benchmark.lua70
1 files changed, 70 insertions, 0 deletions
diff --git a/city/benchmark.lua b/city/benchmark.lua
new file mode 100644
index 0000000..3cba43d
--- /dev/null
+++ b/city/benchmark.lua
@@ -0,0 +1,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)