Реализация карте в F#


Только в качестве освежителя, я собрал простую реализацию карте и я хотел бы получить некоторую обратную связь на нем.

open System
open System.Collections.Generic

type Node<'a, 'b when 'a : comparison> = {
    key : 'a
    value : 'b
    left : option<Node<'a, 'b>>   
    right : option<Node<'a, 'b>>
}

type Map<'a, 'b when 'a : comparison>(root : option<Node<'a, 'b>>) =

    let comparer = LanguagePrimitives.FastGenericComparer<'a>

    let rec add (key : 'a) (value : 'b) (node : Node<'a, 'b>) =
        match comparer.Compare (key, node.key) with
        | r when r < 0 ->
            match node.left with
            | Some n ->
                match comparer.Compare (key, n.key) with
                | r when r > 0 ->
                    let left = Some { 
                        key = key
                        value = value 
                        left = node.left 
                        right = None 
                    }
                    Some { node with left = left }
                | _ ->
                    Some { node with left = add key value n }
            | None ->
                let left = Some { 
                    key = key
                    value = value 
                    left = None 
                    right = None 
                }
                Some { node with left = left }
        | r when r > 0 ->
            match node.right with
            | Some n ->
                match comparer.Compare (key, n.key) with
                | r when r < 0 ->
                    let right = Some { 
                        key = key
                        value = value 
                        left = None 
                        right = node.right 
                    }
                    Some { node with right = right }
                | _ ->
                    Some { node with right = add key value n }
            | None ->
                let right = Some { 
                    key = key
                    value = value 
                    left = None 
                    right = None 
                }
                Some { node with right = right }    
        | _ -> 
            Some { node with value = value }

    let rec find (key : 'a) (node : Node<'a, 'b>) =
        match comparer.Compare (key, node.key) with
        | r when r < 0 ->
            match node.left with
            | Some node -> find key node
            | None -> raise (KeyNotFoundException())
        | r when r > 0 ->
            match node.right with
            | Some node -> find key node
            | None -> raise (KeyNotFoundException())
        | _ -> node.value      

    member x.Item key =
        match root with
        | Some node -> 
            find key node
        | None -> raise (KeyNotFoundException())            

    member x.Add (key : 'a, value : 'b) =
        match root with
        | Some node -> 
            Map (add key value node)
        | None ->
            let node = Some { 
                key = key 
                value = value 
                left = None
                right = None 
            } 
            Map node

    static member Empty = Map<'a, 'b>(None)

    static member FromSeq (s:seq<'a * 'b>) =
        s 
        |> Seq.fold 
            (fun (m:Map<'a, 'b>) (k, v) -> m.Add (k, v)) 
            Map<'a, 'b>.Empty

После выполнения некоторых основных тестов, я нашла свою реализацию сравнима с FSharpMapкласс в производительности, а иногда и лучше. Очевидно, у меня нет времени/желания проверить этот широко так что возьмите это с зерном соли. Я интересно, если кто-либо может заметить особенность этого кода, что повлечет срыв исполнения при определенных условиях или для определенных типов ключей.

Улучшенная Версия

open System
open System.Collections.Generic

type Node<'a, 'b when 'a : comparison> = {
    key : 'a
    value : 'b
    height : int
    left : option<Node<'a, 'b>>   
    right : option<Node<'a, 'b>>
}

type Map<'a, 'b when 'a : comparison>(root : option<Node<'a, 'b>>) =

    let comparer = LanguagePrimitives.FastGenericComparer<'a>    

    let height node =
        match node with
        | Some node -> node.height
        | None -> 0  

    let make key value left right =
        let h = 
            match height left, height right with
            | l, r when l >= r -> l + 1
            | l, r -> r + 1
        Some { 
            key = key; 
            value = value; 
            height = h; 
            left = left; 
            right = right 
        }  

    let balance key value left right =
        match height left, height right with
        | l, r when r > l + 2 ->
            match right with
            | Some rn ->
                match height rn.left with
                | rl when rl <= l + 1 ->
                    let left = make key value left rn.left 
                    make rn.key rn.value left rn.right
                | _ ->
                    match rn.left with
                    | Some rnl ->
                        let left = make key value left rnl.left
                        let right = make rn.key rn.value rnl.right rn.right
                        make rnl.key rnl.value left right
                    | None ->
                        make key value left right
            | None -> 
                make key value left right
        | l, r when l <= r + 2 -> 
            make key value left right
        | l, r ->
            match left with
            | Some ln ->
                match height ln.right with
                | rl when rl <= l + 1 ->
                    let right = make key value ln.right right 
                    make ln.key ln.value ln.left right
                | _ ->
                    match ln.right with
                    | Some lnr ->
                        let left = make ln.key ln.value ln.left lnr.left
                        let right = make key value lnr.right right
                        make lnr.key lnr.value left right
                    | None ->
                        make key value left right
            | None -> 
                make key value left right

    let rec add key value node =
        match comparer.Compare (key, node.key) with
        | r when r < 0 ->
            match node.left with
            | Some n -> 
                balance node.key node.value (add key value n) node.right
            | None ->
                let left = Some { 
                    key = key
                    value = value
                    height = node.height + 1
                    left = None
                    right = None 
                }
                balance node.key node.value left node.right
        | r when r > 0 ->
            match node.right with
            | Some n ->
                balance node.key node.value node.left (add key value n)
            | None ->
                let right = Some { 
                    key = key
                    value = value
                    height = node.height + 1
                    left = None
                    right = None 
                }
                balance node.key node.value node.left right
        | _ -> 
            Some { node with value = value }

    let rec find key node =
        match comparer.Compare (key, node.key) with
        | r when r < 0 ->
            match node.left with
            | Some node -> find key node
            | None -> raise (KeyNotFoundException())
        | r when r > 0 ->
            match node.right with
            | Some node -> find key node
            | None -> raise (KeyNotFoundException())
        | _ -> node.value        

    member x.Item key =
        match root with
        | Some node -> 
            find key node
        | None -> raise (KeyNotFoundException())          

    member x.Add (key, value) =
        match root with
        | Some node -> 
            Map (add key value node)
        | None ->
            let node = Some { 
                key = key 
                value = value 
                height = 1
                left = None
                right = None 
            } 
            Map node

    static member Empty = Map<'a, 'b>(None)

    static member OfSeq (s:seq<'a * 'b>) =
        s 
        |> Seq.fold 
            (fun (m:Map<'a, 'b>) (k, v) -> m.Add (k, v)) 
            Map<'a, 'b>.Empty


788
6
задан 2 марта 2011 в 08:03 Источник Поделиться
Комментарии
1 ответ

Второй пересмотр

Ну, во-первых, это нам очень поможет, если вы добавили некоторые комментарии. Я также предложил бы давать переменным имена, которые имеют более чем одну букву.

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

Кстати: ваше древо рода выглядит как Авл дерево кроме того, что в Авл деревьях максимальная разница между высотами составляет 1, в то время как вы позволяете разницей в 2. Поскольку вы никогда не говорил, что вы пытались реализовать Авл-дерево, я не уверен, является ли это преднамеренным или нет.


Некоторые примечания по конкретной части кода:

match height left, height right with
| l, r when l >= r -> l + 1
| l, r -> r + 1

Вот только громоздкий способ, чтобы написать Макс (высота слева) (высота).


Some {
key = key
value = value
height = node.height + 1
left = None
right = None
}

Это выглядит как ошибка. Если оба поддерева пустые, то ясно, что высота равна 1 и не зависит от узла.


Я бы также порекомендовал, что вместо того, чтобы использовать узел параметрС можно определить реальное дерево типа такой: типа ('а * 'в) дерево = узел (А, Б) узел | EmptyTree. Таким образом, вы можете обратиться к пустым деревьям, как EmptyTree , а чем никто и узлов, а узел {...} , а не какие - { ... }. Конечно, это всего лишь косметика, но я думаю, что он читает гораздо лучше.


Первая ревизия

Один незначительный стиль суть в том, что вы, возможно, захотите, чтобы позвонить своему FromSeq способ ofSeq , а не потому что их эквивалентную функцию f#'ы карту модуль называется.


Что касается производительности, наиболее очевидная проблема заключается в том, что ваше дерево не является сбалансированным в любом случае. Если вы создаете карту с отсортированный список ключей, он вырождается в связанный список и имеют гораздо худшие показатели, чем F#'стандарт класса S карте. Просто сравните время, которое требуется для создания карты от Seq.zip [1..500000] [1..500000] в то время стандартной карте нужны для тех же входных данных.

Для решения этой проблемы необходимо реализовать какой-то балансировки. Например, можно использовать красно-черные деревья, что Ф#'Ы стандартные карты.

8
ответ дан 4 марта 2011 в 08:03 Источник Поделиться