From 6250f10c807301a760b8659f9c00ca6dbbd4c7b7 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Fri, 26 Mar 2021 21:51:03 +0100 Subject: [PATCH] Add the old search for kdTree + benchmark project (for benchmark comparison) --- Parasitemia/Logger/AssemblyInfo.fs | 41 ----------- Parasitemia/Parasitemia.sln | 9 ++- Parasitemia/ParasitemiaCore/KdTree.fs | 30 ++++++++ .../ParasitemiaCore/ParasitemiaCore.fsproj | 2 - Parasitemia/ParasitemiaCore/Types.fs | 3 +- .../ParasitemiaCore.Benchmark.fsproj | 20 ++++++ .../ParasitemiaCore.Benchmark/Program.fs | 70 +++++++++++++++++++ .../ParasitemiaCore.Tests/KdTreeTests.fs | 38 ---------- .../ParasitemiaCore.Tests.fsproj | 8 ++- 9 files changed, 137 insertions(+), 84 deletions(-) delete mode 100644 Parasitemia/Logger/AssemblyInfo.fs create mode 100644 Parasitemia/Tests/ParasitemiaCore.Benchmark/ParasitemiaCore.Benchmark.fsproj create mode 100644 Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs diff --git a/Parasitemia/Logger/AssemblyInfo.fs b/Parasitemia/Logger/AssemblyInfo.fs deleted file mode 100644 index 106b6af..0000000 --- a/Parasitemia/Logger/AssemblyInfo.fs +++ /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. -[] -[] -[] -[] -[] -[] -[] -[] - -// 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. -[] - -// The following GUID is for the ID of the typelib if this project is exposed to COM -[] - -// 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: -// [] -[] -[] - -do - () \ No newline at end of file diff --git a/Parasitemia/Parasitemia.sln b/Parasitemia/Parasitemia.sln index 0a0bad4..66fec92 100644 --- a/Parasitemia/Parasitemia.sln +++ b/Parasitemia/Parasitemia.sln @@ -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} diff --git a/Parasitemia/ParasitemiaCore/KdTree.fs b/Parasitemia/ParasitemiaCore/KdTree.fs index 3a51aac..ec21a0f 100644 --- a/Parasitemia/ParasitemiaCore/KdTree.fs +++ b/Parasitemia/ParasitemiaCore/KdTree.fs @@ -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 + + [] + 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 diff --git a/Parasitemia/ParasitemiaCore/ParasitemiaCore.fsproj b/Parasitemia/ParasitemiaCore/ParasitemiaCore.fsproj index 2825174..aa8ecfb 100644 --- a/Parasitemia/ParasitemiaCore/ParasitemiaCore.fsproj +++ b/Parasitemia/ParasitemiaCore/ParasitemiaCore.fsproj @@ -35,8 +35,6 @@ - - diff --git a/Parasitemia/ParasitemiaCore/Types.fs b/Parasitemia/ParasitemiaCore/Types.fs index 0cb2768..84d4548 100644 --- a/Parasitemia/ParasitemiaCore/Types.fs +++ b/Parasitemia/ParasitemiaCore/Types.fs @@ -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 +[] 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 index 0000000..ea4034b --- /dev/null +++ b/Parasitemia/Tests/ParasitemiaCore.Benchmark/ParasitemiaCore.Benchmark.fsproj @@ -0,0 +1,20 @@ + + + + Exe + net5.0 + + + + + + + + + + + + + + + diff --git a/Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs b/Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs new file mode 100644 index 0000000..5022108 --- /dev/null +++ b/Parasitemia/Tests/ParasitemiaCore.Benchmark/Program.fs @@ -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) + +[] +let main argv = + kdTree () + 0 \ No newline at end of file diff --git a/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs b/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs index ec66fa0..ebf3328 100644 --- a/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs +++ b/Parasitemia/Tests/ParasitemiaCore.Tests/KdTreeTests.fs @@ -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) - [] - 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) diff --git a/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj b/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj index eaa52d3..6ef1b8e 100644 --- a/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj +++ b/Parasitemia/Tests/ParasitemiaCore.Tests/ParasitemiaCore.Tests.fsproj @@ -1,8 +1,9 @@  - Library net5.0 + false + false @@ -10,11 +11,16 @@ + all runtime; build; native; contentfiles; analyzers; buildtransitive + + runtime; build; native; contentfiles; analyzers; buildtransitive + all + -- 2.45.2