From: Greg Burri Date: Sat, 4 Nov 2017 08:34:01 +0000 (+0100) Subject: Add a benchmark test for KdTree (WIP). X-Git-Tag: 1.0.13~15^2 X-Git-Url: http://git.euphorik.ch/?p=master-thesis.git;a=commitdiff_plain;h=05d12f52c42d9d75e7ee3f57c327938180f6b34b Add a benchmark test for KdTree (WIP). --- diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..4a6c7e8 --- /dev/null +++ b/.gitignore @@ -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 index 9181c26..0000000 --- a/Parasitemia/Tests/ParasitemiaCore.Tests/KdTree.fs +++ /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 - [] - 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) - - [] - 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 index 0000000..929dd9e --- /dev/null +++ b/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs @@ -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 + [] + 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) + + [] + 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) + + [] + 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) + + + diff --git a/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj b/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj index 75c810e..3b3cf37 100644 --- a/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj +++ b/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj @@ -51,7 +51,7 @@ - +