Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs

   1 namespace ParasitemiaCore.Tests
   2
   3 open Xunit
   4 open Xunit.Abstractions
   5
   6 open ParasitemiaCore.KdTree
   7
   8 type Point (x : float32, y : float32) =
   9     interface I2DCoords with
  10         member this.X = x
  11         member this.Y = y
  12
  13     override this.ToString () =
  14         sprintf "(%.1f, %.1f)" x y
  15
  16 type KdTreeTests (output : ITestOutputHelper) =
  17
  18     // TODO: test with identical X or Y coords
  19     [<Fact>]
  20     member this.``Test`` () =
  21         let pts =
  22             [
  23                 Point (1.0f, 1.0f)
  24                 Point (2.0f, 2.0f)
  25                 Point (1.5f, 3.6f)
  26                 Point (3.0f, 3.2f)
  27                 Point (4.0f, 4.0f)
  28                 Point (3.5f, 1.5f)
  29                 Point (2.5f, 0.5f)
  30             ]
  31
  32         let tree = Tree.BuildTree pts
  33         output.WriteLine (sprintf "Tree: %A" tree)
  34
  35         let s1 = tree.Search { minX = 0.0f; maxX = 5.0f; minY = 0.0f; maxY = 5.0f } // All points.
  36         output.WriteLine (sprintf "s1: %A" s1)
  37
  38         let s2 = tree.Search { minX = 2.8f; maxX = 4.5f; minY = 3.0f; maxY = 4.5f }
  39         output.WriteLine (sprintf "s2: %A" s2)
  40
  41         let s3 = tree.Search { minX = 2.0f; maxX = 2.0f; minY = 2.0f; maxY = 2.0f }
  42         output.WriteLine (sprintf "s3: %A" s3)
  43
  44     [<Fact>]
  45     member this.``Test 2`` () =
  46         let pts =
  47             [
  48                 Point (1.0f, 1.0f)
  49                 Point (1.0f, 2.0f)
  50                 Point (1.0f, 3.0f)
  51             ]
  52
  53         let tree = Tree.BuildTree pts
  54         output.WriteLine (sprintf "Tree: %A" tree)
  55
  56         let s1 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 1.0f; maxY = 1.0f }
  57         output.WriteLine (sprintf "s1: %A" s1)
  58
  59         let s2 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 2.0f; maxY = 2.0f }
  60         output.WriteLine (sprintf "s2: %A" s2)
  61
  62         // This case result is wrong: FIXME
  63         let s3 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 3.0f; maxY = 3.0f }
  64         output.WriteLine (sprintf "s3: %A" s3)
  65
  66         let s4 = tree.Search { minX = 0.0f; maxX = 2.0f; minY = 0.0f; maxY = 4.0f }
  67         output.WriteLine (sprintf "s4: %A" s4)
  68
  69     [<Fact>]
  70     member this.``Benchmark`` () =
  71         let min = -1_000.
  72         let max = +1_000.
  73         let windowSize = 10.
  74         let nbPoints = 500_000
  75         let n = 1_000
  76
  77         let rng = System.Random 42
  78         let nextNumber (min : float) (max : float) =
  79             (rng.NextDouble () * (max + abs min)) + min |> float32
  80
  81         let points =
  82             [
  83                 for i = 1 to nbPoints do
  84                     let x = nextNumber min max
  85                     let y = nextNumber min max
  86                     Point (x, y)
  87             ]
  88
  89         let sw = System.Diagnostics.Stopwatch ()
  90         sw.Start ()
  91
  92         let tree = Tree.BuildTree points
  93
  94         sw.Stop ()
  95         output.WriteLine (sprintf "Time to build = %A ms" sw.ElapsedMilliseconds)
  96
  97         sw.Restart ()
  98
  99         let mutable nbFound = 0
 100         for i = 1 to n do
 101             let minX = nextNumber min (max - windowSize)
 102             let minY = nextNumber min (max - windowSize)
 103             nbFound <- nbFound + (tree.Search { minX = minX; maxX = minX + float32 windowSize; minY = minY; maxY = minY + float32 windowSize } |> List.length)
 104
 105         sw.Stop ()
 106         output.WriteLine (sprintf "nb found: %i. Time to search = %A ms" nbFound sw.ElapsedMilliseconds)
 107
 108
 109