左斜红黑树的F#代码优化 [英] F# Code Optimization for Left Leaning Red Black Tree
问题描述
我一直在努力将LLRBT的C#实现移植到F#，现在我可以正常运行了.我的问题是如何进行优化?
I've been working on porting a C# implementation of a LLRBT to F# and I now have it running correctly. My question is how would I go about optimizing this?
我有一些想法
- 使用Node的专有联盟来消除对null的使用
- 删除getter和setter
- 您不能同时具有null属性和结构
- Using a Discriminated Union for Node to remove the use of null
- Remove getters and setters
- you cant have a null attribute and a struct at the same time
完整资源可在此处找到. C#代码取自
Full source can be found here. C# code taken from Delay's Blog.
当前性能
F#逝去= 00:00:01.1379927高度:26，计数:487837
C#逝去= 00:00:00.7975849高度:26，计数:487837Current performance
F# Elapsed = 00:00:01.1379927 Height: 26, Count: 487837
C# Elapsed = 00:00:00.7975849 Height: 26, Count: 487837module 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推荐答案
我很惊讶这种性能差异，因为这看起来像是简单的音译.我想两个都是在发布"模式下编译的吗?您是分别运行两个版本(冷启动)，还是两个版本都在同一程序中运行，则颠倒了两者的顺序(例如，热缓存)?做任何分析(具有良好的分析器)?比较内存消耗(甚至fsi.exe也可以帮助解决此问题)?
I'm surprised there's such a perf difference, since this looks like a straightforward transliteration. I presume both are compiled in 'Release' mode? Did you run both separately (cold start), or if both versions in the same program, reverse the order of the two (e.g. warm cache)? Done any profiling (have a good profiler)? Compared memory consumption (even fsi.exe can help with that)?
(对于这种可变的数据结构实现，我看不出有任何明显的改进.)
(I don't see any obvious improvements to be had for this mutable data structure implementation.)
这篇关于左斜红黑树的F#代码优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
