F # Оптимизация кода для Left Leaning Red Black Tree

Question

Я работаю над переносом реализации LLRBT на C# на F #, и теперь у меня это работает правильно. Мой вопрос: как я буду оптимизировать это?

Некоторые идеи у меня есть

• Использование размеченного Союза для узла, чтобы удалить использование нуль
• Удалите методы получения и установки
  • вы не можете иметь нулевой атрибут и на структуру, в то же время

Полный источник можно найти here. Код C#, взятый из 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 

Answer 1

Я удивлен, что существует такая разница в уровне, поскольку это выглядит как простая транслитерация. Я полагаю, оба они скомпилированы в режиме «Release»? Вы запускали оба отдельно (холодный старт) или, если обе версии в одной программе, изменили порядок двух (например, теплый кеш)? Готово ли какое-либо профилирование (есть хороший профилировщик)? По сравнению с потреблением памяти (даже fsi.exe может помочь с этим)?

(я не вижу никаких очевидных улучшений, которые будут иметься для этого изменчивого реализации структуры данных.)

Answer 2

Если вы» желая рассмотреть непреложную реализацию, вы можете взглянуть на статью Криса Окасаки на красно-черных деревьях в функциональной обстановке here.

Answer 3

Я написал непреложный версию, и это работает лучше, чем выше изменчивой один. До сих пор я реализовал только вставку. Я все еще пытаюсь понять, что такое проблемы с производительностью.

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 ->() 
    } 

Answer 4

Мой вопрос, как бы я идти об оптимизации этого?

В изменяемом случае вы должны быть в состоянии получить гораздо более высокую производительность, используя массив Node структур, а не куча выделения каждого отдельного Node. В непреложном случае вы можете попытаться превратить красные узлы в структуры.