代码之家 › 专栏 › 技术社区 › gradbot

f左倾红黑树的代码优化

tree f# optimization

gradbot · 技术社区 · 15 年前

我一直致力于将LLRBT的C实现移植到F,现在我已经让它正确运行了。我的问题是如何优化这个?

我有一些想法

使用节点的区分联合来删除对空值的使用
移除吸气剂和setter
- 不能同时具有空属性和结构

可以找到完整的源 here . 代码取自 Delay's Blog .

当前性能
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

4 回复 | 直到 11 年前

Brian 15 年前

我很惊讶有这么一个性能差异,因为这看起来像一个直白的音译。我想两者都是在“发布”模式下编译的?您是否分别运行这两个版本(冷启动),或者如果两个版本都在同一程序中,请颠倒这两个版本的顺序(例如热缓存)?做过任何分析(有一个好的分析器)?比较内存消耗(即使fsi.exe也能帮助解决这个问题)?

(对于这个可变的数据结构实现,我看不到任何明显的改进。)

gradbot 14 年前

我写了一个不变的版本,它的性能比上面的可变版本要好。到目前为止,我只实现了insert。我仍在努力找出性能问题是什么。

type ILLRBT =
    | Red   of ILLRBT * int * ILLRBT
    | Black of ILLRBT * int * ILLRBT
    | Nil

let flip node = 
    let inline flip node =
        match node with
        |   Red(l, v, r) -> Black(l, v, r)
        | Black(l, v, r) ->   Red(l, v, r)
        | Nil -> Nil
    match node with
    |   Red(l, v, r) -> Black(flip l, v, flip r)
    | Black(l, v, r) ->   Red(flip l, v, flip r)
    | Nil -> Nil

let lRot = function
    |   Red(l, v,   Red(l', v', r'))
    |   Red(l, v, Black(l', v', r')) ->   Red(Red(l, v, l'), v', r')
    | Black(l, v,   Red(l', v', r'))
    | Black(l, v, Black(l', v', r')) -> Black(Red(l, v, l'), v', r')
    | _ -> Nil // could raise an error here

let rRot = function
    |   Red(  Red(l', v', r'), v, r)
    |   Red(Black(l', v', r'), v, r) ->   Red(l', v', Red(r', v, r))
    | Black(  Red(l', v', r'), v, r)
    | Black(Black(l', v', r'), v, r) -> Black(l', v', Red(r', v, r))
    | _ -> Nil // could raise an error here

let rec insert node value = 
    match node with
    | Nil -> Red(Nil, value, Nil)
    | n ->
        n
        |> function
            |   Red(Red(_), v, Red(_))
            | Black(Red(_), v, Red(_)) as node -> flip node
            | x -> x
        |> function
            |   Red(l, v, r) when value < v ->   Red(insert l value, v, r)
            | Black(l, v, r) when value < v -> Black(insert l value, v, r)
            |   Red(l, v, r) when value > v ->   Red(l, v, insert r value)
            | Black(l, v, r) when value > v -> Black(l, v, insert r value)
            | x -> x
        |> function
            |   Red(l, v, Red(_))
            | Black(l, v, Red(_)) as node -> lRot node
            | x -> x
        |> function
            |   Red(Red(Red(_),_,_), v, r)
            | Black(Red(Red(_),_,_), v, r) as node -> rRot node
            | x -> x

let rec iter node =
    seq {
        match node with
        |   Red(l, v, r)
        | Black(l, v, r) ->
            yield! iter l
            yield v
            yield! iter r
        | Nil -> ()
    }

kvb 15 年前

如果您愿意考虑一个不可变的实现,那么您可能想看看ChrisOkasaki在函数设置中关于红黑树的论文。 here .

J D 11 年前

我的问题是如何优化这个?

在可变情况下,您应该能够通过使用 Node 结构而不是堆分配每个单独的 结点 . 在不可变的情况下,您可以尝试将红色节点转换为结构。