我一直在将C#实现的LLRBT移植到F#,现在已经成功运行。我的问题是如何进行优化?
以下是一些想法:
- 使用区分联合类型(Discriminated Union)来移除对null的使用。
- 移除getter和setter
- 你不能同时拥有一个空属性和一个结构体。
当前性能
F# 经过时间 = 00:00:01.1379927 树高:26,节点数:487837
C# 经过时间 = 00:00:00.7975849 树高:26,节点数:487837
module Erik
let Black = true
let Red = false
[<AllowNullLiteralAttribute>]
type Node(_key, _value, _left:Node, _right:Node, _color:bool) =
let mutable key = _key
let mutable value = _value
let mutable left = _left
let mutable right = _right
let mutable color = _color
let mutable siblings = 0
member this.Key with get() = key and set(x) = key <- x
member this.Value with get() = value and set(x) = value <- x
member this.Left with get() = left and set(x) = left <- x
member this.Right with get() = right and set(x) = right <- x
member this.Color with get() = color and set(x) = color <- x
member this.Siblings with get() = siblings and set(x) = siblings <- x
static member inline IsRed(node : Node) =
if node = null then
// "Virtual" leaf nodes are always black
false
else
node.Color = Red
static member inline Flip(node : Node) =
node.Color <- not node.Color
node.Right.Color <- not node.Right.Color
node.Left.Color <- not node.Left.Color
static member inline RotateLeft(node : Node) =
let x = node.Right
node.Right <- x.Left
x.Left <- node
x.Color <- node.Color
node.Color <- Red
x
static member inline RotateRight(node : Node) =
let x = node.Left
node.Left <- x.Right
x.Right <- node
x.Color <- node.Color
node.Color <- Red
x
static member inline MoveRedLeft(_node : Node) =
let mutable node = _node
Node.Flip(node)
if Node.IsRed(node.Right.Left) then
node.Right <- Node.RotateRight(node.Right)
node <- Node.RotateLeft(node)
Node.Flip(node)
if Node.IsRed(node.Right.Right) then
node.Right <- Node.RotateLeft(node.Right)
node
static member inline MoveRedRight(_node : Node) =
let mutable node = _node
Node.Flip(node)
if Node.IsRed(node.Left.Left) then
node <- Node.RotateRight(node)
Node.Flip(node)
node
static member DeleteMinimum(_node : Node) =
let mutable node = _node
if node.Left = null then
null
else
if not(Node.IsRed(node.Left)) && not(Node.IsRed(node.Left.Left)) then
node <- Node.MoveRedLeft(node)
node.Left <- Node.DeleteMinimum(node)
Node.FixUp(node)
static member FixUp(_node : Node) =
let mutable node = _node
if Node.IsRed(node.Right) then
node <- Node.RotateLeft(node)
if Node.IsRed(node.Left) && Node.IsRed(node.Left.Left) then
node <- Node.RotateRight(node)
if Node.IsRed(node.Left) && Node.IsRed(node.Right) then
Node.Flip(node)
if node.Left <> null && Node.IsRed(node.Left.Right) && not(Node.IsRed(node.Left.Left)) then
node.Left <- Node.RotateLeft(node.Left)
if Node.IsRed(node.Left) then
node <- Node.RotateRight(node)
node
type LeftLeaningRedBlackTree(?isMultiDictionary) =
let mutable root = null
let mutable count = 0
member this.IsMultiDictionary =
Option.isSome isMultiDictionary
member this.KeyAndValueComparison(leftKey, leftValue, rightKey, rightValue) =
let comparison = leftKey - rightKey
if comparison = 0 && this.IsMultiDictionary then
leftValue - rightValue
else
comparison
member this.Add(key, value) =
root <- this.add(root, key, value)
member private this.add(_node : Node, key, value) =
let mutable node = _node
if node = null then
count <- count + 1
new Node(key, value, null, null, Red)
else
if Node.IsRed(node.Left) && Node.IsRed(node.Right) then
Node.Flip(node)
let comparison = this.KeyAndValueComparison(key, value, node.Key, node.Value)
if comparison < 0 then
node.Left <- this.add(node.Left, key, value)
elif comparison > 0 then
node.Right <- this.add(node.Right, key, value)
else
if this.IsMultiDictionary then
node.Siblings <- node.Siblings + 1
count <- count + 1
else
node.Value <- value
if Node.IsRed(node.Right) then
node <- Node.RotateLeft(node)
if Node.IsRed(node.Left) && Node.IsRed(node.Left.Left) then
node <- Node.RotateRight(node)
node