Add a benchmark test for KdTree (WIP).
authorGreg Burri <greg.burri@gmail.com>
Sat, 4 Nov 2017 08:34:01 +0000 (09:34 +0100)
committerGreg Burri <greg.burri@gmail.com>
Sat, 4 Nov 2017 08:34:01 +0000 (09:34 +0100)
.gitignore [new file with mode: 0644]
Parasitemia/Tests/ParasitemiaCore.Tests/KdTree.fs [deleted file]
Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs [new file with mode: 0644]
Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
index 0000000..4a6c7e8
--- /dev/null
@@ -0,0 +1,6 @@
+bin/
+obj/
+packages/
+.vs
+*.exe
+*.suo
\ No newline at end of file
diff --git a/Parasitemia/Tests/ParasitemiaCore.Tests/KdTree.fs b/Parasitemia/Tests/ParasitemiaCore.Tests/KdTree.fs
deleted file mode 100644 (file)
index 9181c26..0000000
+++ /dev/null
@@ -1,71 +0,0 @@
-namespace ParasitemiaCore.Tests
-
-open Xunit
-open Xunit.Abstractions
-
-open ParasitemiaCore.KdTree
-
-type Point (x : float32, y : float32) =
-    interface I2DCoords with
-        member this.X = x
-        member this.Y = y
-
-    override this.ToString () =
-        sprintf "(%.1f, %.1f)" x y
-
-type KdTreeTests (output : ITestOutputHelper) =
-
-    // TODO: test with identical X or Y coords
-    [<Fact>]
-    member this.test () =
-        let pts =
-            [
-                Point (1.0f, 1.0f)
-                Point (2.0f, 2.0f)
-                Point (1.5f, 3.6f)
-                Point (3.0f, 3.2f)
-                Point (4.0f, 4.0f)
-                Point (3.5f, 1.5f)
-                Point (2.5f, 0.5f)
-            ]
-
-        let tree = Tree.BuildTree pts
-        output.WriteLine (sprintf "Tree: %A" tree)
-
-        let s1 = tree.Search { minX = 0.0f; maxX = 5.0f; minY = 0.0f; maxY = 5.0f } // All points.
-        output.WriteLine (sprintf "s1: %A" s1)
-
-        let s2 = tree.Search { minX = 2.8f; maxX = 4.5f; minY = 3.0f; maxY = 4.5f }
-        output.WriteLine (sprintf "s2: %A" s2)
-
-        let s3 = tree.Search { minX = 2.0f; maxX = 2.0f; minY = 2.0f; maxY = 2.0f }
-        output.WriteLine (sprintf "s3: %A" s3)
-
-    [<Fact>]
-    member this.test2 () =
-        let pts =
-            [
-                Point (1.0f, 1.0f)
-                Point (1.0f, 2.0f)
-                Point (1.0f, 3.0f)
-            ]
-
-        let tree = Tree.BuildTree pts
-        output.WriteLine (sprintf "Tree: %A" tree)
-
-        let s1 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 1.0f; maxY = 1.0f }
-        output.WriteLine (sprintf "s1: %A" s1)
-
-        let s2 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 2.0f; maxY = 2.0f }
-        output.WriteLine (sprintf "s2: %A" s2)
-
-        // This case result is wrong: FIXME
-        let s3 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 3.0f; maxY = 3.0f }
-        output.WriteLine (sprintf "s3: %A" s3)
-
-        let s4 = tree.Search { minX = 0.0f; maxX = 2.0f; minY = 0.0f; maxY = 4.0f }
-        output.WriteLine (sprintf "s4: %A" s4)
-
-
-
-
diff --git a/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs b/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs
new file mode 100644 (file)
index 0000000..929dd9e
--- /dev/null
@@ -0,0 +1,98 @@
+namespace ParasitemiaCore.Tests
+
+open Xunit
+open Xunit.Abstractions
+
+open ParasitemiaCore.KdTree
+
+type Point (x : float32, y : float32) =
+    interface I2DCoords with
+        member this.X = x
+        member this.Y = y
+
+    override this.ToString () =
+        sprintf "(%.1f, %.1f)" x y
+
+type KdTreeTests (output : ITestOutputHelper) =
+
+    // TODO: test with identical X or Y coords
+    [<Fact>]
+    member this.``Test`` () =
+        let pts =
+            [
+                Point (1.0f, 1.0f)
+                Point (2.0f, 2.0f)
+                Point (1.5f, 3.6f)
+                Point (3.0f, 3.2f)
+                Point (4.0f, 4.0f)
+                Point (3.5f, 1.5f)
+                Point (2.5f, 0.5f)
+            ]
+
+        let tree = Tree.BuildTree pts
+        output.WriteLine (sprintf "Tree: %A" tree)
+
+        let s1 = tree.Search { minX = 0.0f; maxX = 5.0f; minY = 0.0f; maxY = 5.0f } // All points.
+        output.WriteLine (sprintf "s1: %A" s1)
+
+        let s2 = tree.Search { minX = 2.8f; maxX = 4.5f; minY = 3.0f; maxY = 4.5f }
+        output.WriteLine (sprintf "s2: %A" s2)
+
+        let s3 = tree.Search { minX = 2.0f; maxX = 2.0f; minY = 2.0f; maxY = 2.0f }
+        output.WriteLine (sprintf "s3: %A" s3)
+
+    [<Fact>]
+    member this.``Test 2`` () =
+        let pts =
+            [
+                Point (1.0f, 1.0f)
+                Point (1.0f, 2.0f)
+                Point (1.0f, 3.0f)
+            ]
+
+        let tree = Tree.BuildTree pts
+        output.WriteLine (sprintf "Tree: %A" tree)
+
+        let s1 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 1.0f; maxY = 1.0f }
+        output.WriteLine (sprintf "s1: %A" s1)
+
+        let s2 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 2.0f; maxY = 2.0f }
+        output.WriteLine (sprintf "s2: %A" s2)
+
+        // This case result is wrong: FIXME
+        let s3 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 3.0f; maxY = 3.0f }
+        output.WriteLine (sprintf "s3: %A" s3)
+
+        let s4 = tree.Search { minX = 0.0f; maxX = 2.0f; minY = 0.0f; maxY = 4.0f }
+        output.WriteLine (sprintf "s4: %A" s4)
+
+    [<Fact>]
+    member this.``Benchmark`` () =
+        let min = -1_000.
+        let max = +1_000.
+        let windowSize = 10.
+
+        let rng = System.Random 42
+        let nextNumber (min : float) (max : float) =
+            (rng.NextDouble () * (max + abs min)) + min |> float32
+
+        let points =
+            [
+                for i = 1 to 200_000 do
+                    let x = nextNumber min max
+                    let y = nextNumber min max
+                    yield Point (x, y)
+            ]
+
+        let tree = Tree.BuildTree points
+
+        let mutable nb = 0
+        for i = 1 to 1_000 do
+            let minX = nextNumber min (max - windowSize)
+            let minY = nextNumber min (max - windowSize)
+            nb <- nb + (tree.Search { minX = minX; maxX = minX + float32 windowSize; minY = minY; maxY = minY + float32 windowSize } |> List.length)
+
+        output.WriteLine (sprintf "nb: %A" nb)
+
+
+
index 75c810e..3b3cf37 100644 (file)
@@ -51,7 +51,7 @@
   <ItemGroup>
     <Compile Include="AssemblyInfo.fs" />
     <Content Include="packages.config" />
   <ItemGroup>
     <Compile Include="AssemblyInfo.fs" />
     <Content Include="packages.config" />
-    <Compile Include="KdTree.fs" />
+    <Compile Include="KdTreeTests.fs" />
   </ItemGroup>
   <ItemGroup>
     <Reference Include="FSharp.Core">
   </ItemGroup>
   <ItemGroup>
     <Reference Include="FSharp.Core">