From ac4d3ee05f84d293524ea51a1df43db0060b6fd3 Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Fri, 25 Feb 2022 14:40:05 -0600
Subject: add benchmark.lua

---
 city/benchmark.lua | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 city/benchmark.lua

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)
-- 
cgit v1.2.1