Replace F# list by List<T> for KdTree.
authorGreg Burri <greg.burri@gmail.com>
Thu, 25 Mar 2021 10:28:44 +0000 (11:28 +0100)
committerGreg Burri <greg.burri@gmail.com>
Thu, 25 Mar 2021 10:28:44 +0000 (11:28 +0100)
It doesn't seem to improve a lot the execution speed -> investigate.

Parasitemia/ParasitemiaCore/Classifier.fs
Parasitemia/ParasitemiaCore/KdTree.fs

index 475e336..b01a041 100644 (file)
@@ -90,7 +90,7 @@ let findCells (ellipses : Ellipse list) (parasites : ParasitesMarker.Result) (wi
             if e.State <> CellState.Removed then
                 tree.Search (searchRegion e)
                     // We only keep the ellipses touching 'e'.
-                    |> List.choose (
+                    |> Seq.choose (
                         fun otherE ->
                             if e <> otherE then
                                 match EEOver.EEOverlapArea e otherE with
@@ -104,6 +104,7 @@ let findCells (ellipses : Ellipse list) (parasites : ParasitesMarker.Result) (wi
                             else
                                 None
                     )
+                    |> List.ofSeq
             else
                 []
 
index 2525e27..3a51aac 100644 (file)
@@ -1,6 +1,7 @@
 module ParasitemiaCore.KdTree
 
 open System
+open System.Collections.Generic
 
 type I2DCoords =
     abstract X : float32
@@ -62,31 +63,34 @@ type Tree<'a when 'a :> I2DCoords> =
 
         buildTreeFromSortedArray xSorted ySorted 1
 
-    member this.Search (searchRegion : Region) : 'a list =
-        let rec valuesFrom (tree : Tree<'a>) (acc : 'a list) : 'a list =
+    member this.Search (searchRegion : Region) : List<'a> =
+        let result = List<'a> ()
+        let rec valuesFrom (tree : Tree<'a>) =
             match tree with
-            | Node (_, left, right) -> (valuesFrom right (valuesFrom left acc))
-            | Leaf v -> v :: acc
+            | Node (_, left, right) ->
+                valuesFrom right
+                valuesFrom left
+            | Leaf v ->
+                result.Add v
 
-        let rec searchWithRegion (tree : Tree<'a>) (currentRegion : Region) (depth : int) : 'a list =
+        let rec searchWithRegion (tree : Tree<'a>) (currentRegion : Region) (depth : int) =
             match tree with
-            | Leaf v -> if searchRegion.Contains v.X v.Y then [v] else []
+            | Leaf v ->
+                if searchRegion.Contains v.X v.Y then
+                    result.Add v
             | Node (splitValue, part1, part2) ->
-                let valuesInRegion (region : Region) (treeRegion : Tree<'a>) =
+                let inline valuesInRegion (region : Region) (treeRegion : Tree<'a>) =
                     if region.IsSub searchRegion then
-                        valuesFrom treeRegion []
+                        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)
+                    valuesInRegion { currentRegion with maxX = splitValue } part1 // Left region.
+                    valuesInRegion { currentRegion with minX = splitValue } part2 // Right region.
                 else // Horizontal splitting.
-                    let downRegion = { currentRegion with maxY = splitValue }
-                    let upRegion = { currentRegion with minY = splitValue }
-                    (valuesInRegion downRegion part1) @ (valuesInRegion upRegion part2)
+                    valuesInRegion { currentRegion with maxY = splitValue } part1 // Down region.
+                    valuesInRegion { currentRegion with minY = splitValue } part2 // Up region.
 
         searchWithRegion this { minX = Single.MinValue; maxX = Single.MaxValue; minY = Single.MinValue; maxY = Single.MaxValue } 1
+        result