projects
/
master-thesis.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Cleaning, micro-optimizations.
[master-thesis.git]
/
Parasitemia
/
Parasitemia
/
Heap.fs
diff --git
a/Parasitemia/Parasitemia/Heap.fs
b/Parasitemia/Parasitemia/Heap.fs
index
82298e2
..
3d0879e
100644
(file)
--- a/
Parasitemia/Parasitemia/Heap.fs
+++ b/
Parasitemia/Parasitemia/Heap.fs
@@
-6,8
+6,11
@@
let inline private parent (i: int) : int = (i - 1) / 2
let inline private left (i: int) : int = 2 * (i + 1) - 1
let inline private right (i: int) : int = 2 * (i + 1)
let inline private left (i: int) : int = 2 * (i + 1) - 1
let inline private right (i: int) : int = 2 * (i + 1)
-// TODO: measure performance with a struct.
-type private Node<'k, 'v> = { mutable key: 'k; value : 'v } with
+[<Struct>]
+type private Node<'k, 'v> =
+ val mutable key: 'k
+ val value: 'v
+ new (k, v) = { key = k; value = v }
override this.ToString () = sprintf "%A -> %A" this.key this.value
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
override this.ToString () = sprintf "%A -> %A" this.key this.value
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
@@
-32,9
+35,9
@@
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
a.[max] <- tmp
heapUp max
a.[max] <- tmp
heapUp max
+ // Check the integrity of the heap, use for debug only.
let rec checkIntegrity (i: int) : bool =
let l, r = left i, right i
let rec checkIntegrity (i: int) : bool =
let l, r = left i, right i
-
let leftIntegrity =
if l < a.Count
then
let leftIntegrity =
if l < a.Count
then
@@
-62,11
+65,11
@@
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
(this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
member this.Next () : 'k * 'v =
(this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
member this.Next () : 'k * 'v =
- let
{ key = key; value = value }
= a.[0]
+ let
node
= a.[0]
a.[0] <- a.[a.Count - 1]
a.RemoveAt(a.Count - 1)
heapUp 0
a.[0] <- a.[a.Count - 1]
a.RemoveAt(a.Count - 1)
heapUp 0
-
key,
value
+
node.key, node.
value
member this.RemoveNext () =
a.[0] <- a.[a.Count - 1]
member this.RemoveNext () =
a.[0] <- a.[a.Count - 1]
@@
-74,7
+77,7
@@
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
heapUp 0
member this.Add (key: 'k) (value: 'v) =
heapUp 0
member this.Add (key: 'k) (value: 'v) =
- a.Add(
{ key = key; value = value }
)
+ a.Add(
Node(key, value)
)
let mutable i = a.Count - 1
while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do
let mutable i = a.Count - 1
while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do