Add the old search for kdTree + benchmark project
authorGreg Burri <greg.burri@gmail.com>
Fri, 26 Mar 2021 20:51:03 +0000 (21:51 +0100)
committerGreg Burri <greg.burri@gmail.com>
Fri, 26 Mar 2021 20:51:03 +0000 (21:51 +0100)
(for benchmark comparison)

Parasitemia/Logger/AssemblyInfo.fs [deleted file]
Parasitemia/Parasitemia.sln
Parasitemia/ParasitemiaCore/KdTree.fs
Parasitemia/ParasitemiaCore/ParasitemiaCore.fsproj
Parasitemia/ParasitemiaCore/Types.fs
Parasitemia/Tests/ParasitemiaCore.Benchmark/ParasitemiaCore.Benchmark.fsproj [new file with mode: 0644]
Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs [new file with mode: 0644]
Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs
Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj

diff --git a/Parasitemia/Logger/AssemblyInfo.fs b/Parasitemia/Logger/AssemblyInfo.fs
deleted file mode 100644 (file)
index 106b6af..0000000
+++ /dev/null
@@ -1,41 +0,0 @@
-namespace Logger.AssemblyInfo
-
-open System.Reflection
-open System.Runtime.CompilerServices
-open System.Runtime.InteropServices
-
-// General Information about an assembly is controlled through the following 
-// set of attributes. Change these attribute values to modify the information
-// associated with an assembly.
-[<assembly: AssemblyTitle "Logger">]
-[<assembly: AssemblyDescription "">]
-[<assembly: AssemblyConfiguration "">]
-[<assembly: AssemblyCompany "">]
-[<assembly: AssemblyProduct "Logger">]
-[<assembly: AssemblyCopyright "Copyright ©  2016">]
-[<assembly: AssemblyTrademark "">]
-[<assembly: AssemblyCulture "">]
-
-// Setting ComVisible to false makes the types in this assembly not visible 
-// to COM components.  If you need to access a type in this assembly from 
-// COM, set the ComVisible attribute to true on that type.
-[<assembly: ComVisible false>]
-
-// The following GUID is for the ID of the typelib if this project is exposed to COM
-[<assembly: Guid "a4f183ae-562a-4bad-88e6-658b4ce15dc3">]
-
-// Version information for an assembly consists of the following four values:
-// 
-//       Major Version
-//       Minor Version 
-//       Build Number
-//       Revision
-// 
-// You can specify all the values or you can default the Build and Revision Numbers 
-// by using the '*' as shown below:
-// [<assembly: AssemblyVersion "1.0.*">]
-[<assembly: AssemblyVersion "1.0.0.0">]
-[<assembly: AssemblyFileVersion "1.0.0.0">]
-
-do
-    ()
\ No newline at end of file
index 0a0bad4..66fec92 100644 (file)
@@ -11,10 +11,12 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "ParasitemiaCore", "Parasite
 EndProject
 Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Tests", "Tests", "{1EC5C716-CA52-46FD-A76C-BEF9459E5561}"
 EndProject
-Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "ParasitemiaCore.Tests", "Tests\ParasitemiaCore.Tests\ParasitemiaCore.Tests.fsproj", "{2AB542E3-5F90-48CA-9442-32B2780B3E4A}"
+Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "ParasitemiaCore.Tests", "Tests\ParasitemiaCore.Tests\ParasitemiaCore.Tests.fsproj", "{2AB542E3-5F90-48CA-9442-32B2780B3E4A}"
 EndProject
 Project("{9A19103F-16F7-4668-BE54-9A1E7A4F7556}") = "ParasitemiaUIControls", "ParasitemiaUIControls\ParasitemiaUIControls.csproj", "{98E21672-B520-4CBA-86C7-6A0856367A10}"
 EndProject
+Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "ParasitemiaCore.Benchmark", "Tests\ParasitemiaCore.Benchmark\ParasitemiaCore.Benchmark.fsproj", "{81CEE3C6-BA65-4063-9A89-97F3208E689C}"
+EndProject
 Global
        GlobalSection(SolutionConfigurationPlatforms) = preSolution
                Debug|Any CPU = Debug|Any CPU
@@ -41,12 +43,17 @@ Global
                {98E21672-B520-4CBA-86C7-6A0856367A10}.Debug|Any CPU.Build.0 = Debug|Any CPU
                {98E21672-B520-4CBA-86C7-6A0856367A10}.Release|Any CPU.ActiveCfg = Release|Any CPU
                {98E21672-B520-4CBA-86C7-6A0856367A10}.Release|Any CPU.Build.0 = Release|Any CPU
+               {81CEE3C6-BA65-4063-9A89-97F3208E689C}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+               {81CEE3C6-BA65-4063-9A89-97F3208E689C}.Debug|Any CPU.Build.0 = Debug|Any CPU
+               {81CEE3C6-BA65-4063-9A89-97F3208E689C}.Release|Any CPU.ActiveCfg = Release|Any CPU
+               {81CEE3C6-BA65-4063-9A89-97F3208E689C}.Release|Any CPU.Build.0 = Release|Any CPU
        EndGlobalSection
        GlobalSection(SolutionProperties) = preSolution
                HideSolutionNode = FALSE
        EndGlobalSection
        GlobalSection(NestedProjects) = preSolution
                {2AB542E3-5F90-48CA-9442-32B2780B3E4A} = {1EC5C716-CA52-46FD-A76C-BEF9459E5561}
+               {81CEE3C6-BA65-4063-9A89-97F3208E689C} = {1EC5C716-CA52-46FD-A76C-BEF9459E5561}
        EndGlobalSection
        GlobalSection(ExtensibilityGlobals) = postSolution
                SolutionGuid = {EE42D93F-9364-4E6D-8D65-A065EEDB5733}
index 3a51aac..ec21a0f 100644 (file)
@@ -94,3 +94,33 @@ type Tree<'a when 'a :> I2DCoords> =
 
         searchWithRegion this { minX = Single.MinValue; maxX = Single.MaxValue; minY = Single.MinValue; maxY = Single.MaxValue } 1
         result
+
+    [<Obsolete>]
+    member this.SearchOld (searchRegion : Region) : 'a list =
+        let rec valuesFrom (tree : Tree<'a>) (acc : 'a list) : 'a list =
+            match tree with
+            | Node (_, left, right) -> (valuesFrom right (valuesFrom left acc))
+            | Leaf v -> v :: acc
+
+        let rec searchWithRegion (tree : Tree<'a>) (currentRegion : Region) (depth : int) : 'a list =
+            match tree with
+            | Leaf v -> if searchRegion.Contains v.X v.Y then [v] else []
+            | Node (splitValue, part1, part2) ->
+                let valuesInRegion (region : Region) (treeRegion : Tree<'a>) =
+                    if region.IsSub searchRegion then
+                        valuesFrom treeRegion []
+                    elif region.Intersects searchRegion then
+                        searchWithRegion treeRegion region (depth + 1)
+                    else
+                        []
+
+                if depth % 2 = 1 then // Vertical splitting.
+                    let leftRegion = { currentRegion with maxX = splitValue }
+                    let rightRegion = { currentRegion with minX = splitValue }
+                    (valuesInRegion leftRegion part1) @ (valuesInRegion rightRegion part2)
+                else // Horizontal splitting.
+                    let downRegion = { currentRegion with maxY = splitValue }
+                    let upRegion = { currentRegion with minY = splitValue }
+                    (valuesInRegion downRegion part1) @ (valuesInRegion upRegion part2)
+
+        searchWithRegion this { minX = Single.MinValue; maxX = Single.MaxValue; minY = Single.MinValue; maxY = Single.MaxValue } 1
index 2825174..aa8ecfb 100644 (file)
@@ -35,8 +35,6 @@
     <Compile Include="Ellipse.fs" />
     <Compile Include="Classifier.fs" />
     <Compile Include="Analysis.fs" />
-    <Content Include="License-LGPL.txt" />
-    <Content Include="OpenTK.dll.config" />
   </ItemGroup>
 
   <ItemGroup>
index 0cb2768..84d4548 100644 (file)
@@ -46,6 +46,7 @@ type Ellipse (cx : float32, cy : float32, a : float32, b : float32, alpha : floa
     override this.ToString () =
         sprintf "{Ellipse: cx = %f, cy = %f, a = %f, b = %f, alpha = %f}" this.Cx this.Cy this.A this.B this.Alpha
 
+[<Struct>]
 type CellClass = HealthyRBC | InfectedRBC | Peculiar
 
 type Cell =
@@ -105,7 +106,7 @@ type ResultBuilder () =
 
 let result = ResultBuilder ()
 
-type AnalysisResult = 
+type AnalysisResult =
     {
         Cells : Cell list
         RBCSize_μm : float<μm>
diff --git a/Parasitemia/Tests/ParasitemiaCore.Benchmark/ParasitemiaCore.Benchmark.fsproj b/Parasitemia/Tests/ParasitemiaCore.Benchmark/ParasitemiaCore.Benchmark.fsproj
new file mode 100644 (file)
index 0000000..ea4034b
--- /dev/null
@@ -0,0 +1,20 @@
+<Project Sdk="Microsoft.NET.Sdk">
+
+  <PropertyGroup>
+    <OutputType>Exe</OutputType>
+    <TargetFramework>net5.0</TargetFramework>
+  </PropertyGroup>
+
+  <ItemGroup>
+    <Compile Include="Program.fs" />
+  </ItemGroup>
+
+  <ItemGroup>
+    <ProjectReference Include="..\ParasitemiaCore.Tests\ParasitemiaCore.Tests.fsproj" />
+  </ItemGroup>
+
+  <ItemGroup>
+    <PackageReference Update="FSharp.Core" Version="5.0.1" />
+  </ItemGroup>
+
+</Project>
diff --git a/Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs b/Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs
new file mode 100644 (file)
index 0000000..5022108
--- /dev/null
@@ -0,0 +1,70 @@
+// Learn more about F# at http://docs.microsoft.com/dotnet/fsharp
+
+open System
+open type System.Console
+
+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
+
+let kdTree () =
+    let min = -1_000.
+    let max = +1_000.
+    let windowSize = 10.
+    let nbPoints = 1_000_000
+    let n = 1_000_000
+
+    let rng = Random 42
+    let nextNumber (min : float) (max : float) (rng : Random) =
+        (rng.NextDouble () * (max + abs min)) + min |> float32
+
+    let points =
+        [
+            for i = 1 to nbPoints do
+                let x = nextNumber min max rng
+                let y = nextNumber min max rng
+                Point (x, y)
+        ]
+
+    let sw = System.Diagnostics.Stopwatch ()
+    sw.Start ()
+
+    let tree = Tree.BuildTree points
+
+    sw.Stop ()
+    WriteLine (sprintf "Time to build = %A ms" sw.ElapsedMilliseconds)
+
+    let rng = Random 42
+    sw.Restart ()
+
+    let mutable nbFound = 0
+    for i = 1 to n do
+        let minX = nextNumber min (max - windowSize) rng
+        let minY = nextNumber min (max - windowSize) rng
+        nbFound <- nbFound + (tree.SearchOld { minX = minX; maxX = minX + float32 windowSize; minY = minY; maxY = minY + float32 windowSize } |> List.length)
+
+    sw.Stop ()
+    WriteLine (sprintf "New: nb found: %i. Time to search = %A ms" nbFound sw.ElapsedMilliseconds)
+
+    let rng = Random 42
+    sw.Restart ()
+
+    let mutable nbFound = 0
+    for i = 1 to n do
+        let minX = nextNumber min (max - windowSize) rng
+        let minY = nextNumber min (max - windowSize) rng
+        nbFound <- nbFound + (tree.Search { minX = minX; maxX = minX + float32 windowSize; minY = minY; maxY = minY + float32 windowSize }).Count
+
+    sw.Stop ()
+    WriteLine (sprintf "New: nb found: %i. Time to search = %A ms" nbFound sw.ElapsedMilliseconds)
+
+[<EntryPoint>]
+let main argv =
+    kdTree ()
+    0
\ No newline at end of file
index ec66fa0..ebf3328 100644 (file)
@@ -66,44 +66,6 @@ type KdTreeTests (output : ITestOutputHelper) =
         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 nbPoints = 500_000
-        let n = 1_000
-
-        let rng = System.Random 42
-        let nextNumber (min : float) (max : float) =
-            (rng.NextDouble () * (max + abs min)) + min |> float32
-
-        let points =
-            [
-                for i = 1 to nbPoints do
-                    let x = nextNumber min max
-                    let y = nextNumber min max
-                    Point (x, y)
-            ]
-
-        let sw = System.Diagnostics.Stopwatch ()
-        sw.Start ()
-
-        let tree = Tree.BuildTree points
-
-        sw.Stop ()
-        output.WriteLine (sprintf "Time to build = %A ms" sw.ElapsedMilliseconds)
-
-        sw.Restart ()
-
-        let mutable nbFound = 0
-        for i = 1 to n do
-            let minX = nextNumber min (max - windowSize)
-            let minY = nextNumber min (max - windowSize)
-            nbFound <- nbFound + (tree.Search { minX = minX; maxX = minX + float32 windowSize; minY = minY; maxY = minY + float32 windowSize } |> List.length)
-
-        sw.Stop ()
-        output.WriteLine (sprintf "nb found: %i. Time to search = %A ms" nbFound sw.ElapsedMilliseconds)
 
 
 
index eaa52d3..6ef1b8e 100644 (file)
@@ -1,8 +1,9 @@
 <Project Sdk="Microsoft.NET.Sdk">
 
   <PropertyGroup>
-    <OutputType>Library</OutputType>
     <TargetFramework>net5.0</TargetFramework>
+    <IsPackable>false</IsPackable>
+    <GenerateProgramFile>false</GenerateProgramFile>
   </PropertyGroup>
 
   <ItemGroup>
   </ItemGroup>
 
   <ItemGroup>
+    <PackageReference Include="Microsoft.NET.Test.Sdk" Version="16.9.1" />
     <PackageReference Include="xunit" Version="2.4.1" />
     <PackageReference Include="xunit.runner.visualstudio" Version="2.4.3">
       <PrivateAssets>all</PrivateAssets>
       <IncludeAssets>runtime; build; native; contentfiles; analyzers; buildtransitive</IncludeAssets>
     </PackageReference>
+    <PackageReference Include="coverlet.collector" Version="3.0.3">
+      <IncludeAssets>runtime; build; native; contentfiles; analyzers; buildtransitive</IncludeAssets>
+      <PrivateAssets>all</PrivateAssets>
+    </PackageReference>
   </ItemGroup>
 
   <ItemGroup>