Почему мой поиск в Trie медленнее, чем в стандартной F# Map?

Итак, я просто портировал Trie из OCaml. К сожалению, он работает медленнее, чем стандартная карта с точки зрения tryFind. Я не понимаю этого - кажется, что это должно быть быстрее. Созданы ли библиотеки кода F# каким-то особым образом, чтобы сделать их быстрее, чем код, который обычно развертывает пользователь?

Вот код -

[<RequireQualifiedAccess>]
module Trie

type Node<'k, 'v when 'k : comparison> =
    { TrieMap : Map<'k, Node<'k, 'v>>
      TrieKvp : ('k list * 'v) option }
    member inline x.IsEmpty = x.TrieKvp.IsNone && x.TrieMap.IsEmpty

let inline make map kvp =
    { TrieMap = map
      TrieKvp = kvp }

let inline makeEmpty () : Node<'k, 'v> = make Map.empty None

let inline isEmpty (node : Node<'k, 'v>) = node.IsEmpty

let rec tryFind (key : 'k list) node =
    if key.IsEmpty then
        match node.TrieKvp with
        | Some (_, value) -> Some value
        | None -> None
    else
        let keyHead = key.Head
        let keyTail = key.Tail
        let optSubNode = Map.tryFind keyHead node.TrieMap
        match optSubNode with
        | Some subNode -> tryFind keyTail subNode
        | None -> None

let inline containsKey key node =
    (tryFind key node).IsSome

let rec addInternal (key : 'k list) value node =
    if key.IsEmpty then make node.TrieMap (Some (key, value))
    else
        let keyHead = key.Head
        let keyTail = key.Tail
        let newTrie =
            match Map.tryFind keyHead node.TrieMap with
            | Some subTrie -> subTrie
            | None -> makeEmpty ()
        let newTrie2 = addInternal keyTail value newTrie
        make (Map.add keyHead newTrie2 node.TrieMap) node.TrieKvp

let inline add key value node =
    addInternal key value node

let rec addMany kvps node =
    if Seq.isEmpty kvps then node
    else
        let kvpHead = Seq.head kvps
        let kvpTail = Seq.skip 1 kvps
        let newTrie = add (fst kvpHead) (snd kvpHead) node
        addMany kvpTail newTrie

let inline ofList kvps =
    addMany kvps (makeEmpty ())

let inline ofListBy by kvps =
    let pairs = List.map by kvps
    ofList pairs

let rec foldInternal folder rev node state =
    match node.TrieKvp with
    | Some (_, value) -> folder (Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap) (List.rev rev) value
    | None -> Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap

let inline fold folder state node =
    foldInternal folder [] node state

let rec map (mapper : 'k list -> 'v -> 'a) (node : Node<'k, 'v>) : Node<'k, 'a> =
    match node.TrieKvp with
    | Some (key, value) -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) (Some (key, mapper key value))
    | None -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) None

let inline toValueList node =
    fold (fun state _ value -> value :: state) [] node

let inline singleton (key, value) =
    add key value (makeEmpty ())

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

let xs = Array.init 1000000 (fun i -> [i])
let timer = System.Diagnostics.Stopwatch.StartNew()
let mutable t = Trie.makeEmpty()
for i=0 to xs.Length-1 do
    t <- Trie.add xs.[i] xs.[i] t
printfn "Trie took %fs to build" timer.Elapsed.TotalSeconds
timer.Restart()
for _ in 1..100 do
    for i=0 to xs.Length-1 do
        ignore(Trie.tryFind xs.[i])
printfn "Trie took %fs to search" timer.Elapsed.TotalSeconds

let timer = System.Diagnostics.Stopwatch.StartNew()
let mutable t = Map.empty
for i=0 to xs.Length-1 do
    t <- Map.add xs.[i] xs.[i] t
printfn "Map took %fs to build" timer.Elapsed.TotalSeconds
timer.Restart()
for _ in 1..100 do
    for i=0 to xs.Length-1 do
        ignore(Map.tryFind xs.[i])
printfn "Map took %fs to search" timer.Elapsed.TotalSeconds

ПРИМЕЧАНИЕ: если вы имеете в виду более быструю структуру поиска данных, обратите внимание, что мне нужна постоянная структура данных.

Источник

3 ответа

Решение

К сожалению, он работает медленнее, чем стандартная карта с точки зрения tryFind. Я не понимаю этого - кажется, что это должно быть быстрее.

Быстрый тест здесь показывает, что ваша программа уже быстрее, чем Map по крайней мере, в простом случае:

do
    let n = 0
    let xs = Array.init 1000000 (fun i -> [i])
    let timer = System.Diagnostics.Stopwatch.StartNew()
    let mutable t = Trie.makeEmpty()
    for i=0 to xs.Length-1 do
        t <- Trie.add xs.[i] xs.[i] t
    printfn "Trie took %fs to build" timer.Elapsed.TotalSeconds
    timer.Restart()
    for _ in 1..100 do
        for i=0 to xs.Length-1 do
            ignore(Trie.tryFind xs.[i])
    printfn "Trie took %fs to search" timer.Elapsed.TotalSeconds

    let timer = System.Diagnostics.Stopwatch.StartNew()
    let mutable t = Map.empty
    for i=0 to xs.Length-1 do
        t <- Map.add xs.[i] xs.[i] t
    printfn "Map took %fs to build" timer.Elapsed.TotalSeconds
    timer.Restart()
    for _ in 1..100 do
        for i=0 to xs.Length-1 do
            ignore(Map.tryFind xs.[i])
    printfn "Map took %fs to search" timer.Elapsed.TotalSeconds

Я получаю 4s, чтобы построить ваш Trie, 8.7s, чтобы построить Map и о 0.7 искать в обоих случаях.

Тем не менее, есть много возможностей для улучшения вашей реализации. Недавно я написал статью об оптимизированной реализации универсального постоянного хеш-кода в F#, которая была опубликована здесь.

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

РЕДАКТИРОВАТЬ

KVB предложил мне подробно остановиться на "комнате для улучшений", так что вот несколько отзывов:

  • использование inline экономно, как оптимизация и только на основе убедительных измерений производительности.
  • Делать empty значение, а не функция.
  • избежать List.head а также List.tail когда возможно. Вместо этого используйте сопоставление с образцом.
  • Избегайте универсальности, когда это возможно (например, жесткий код для строковых ключей в этом случае).
Источник

Хорошо, поэтому, немного подумав, я предположил, что реальная разница в производительности заключается в использовании списков для ключей, а не строк. Строки (и массив) имеют гораздо лучшую когерентность кеша. Итак, я изменил ключ из списка 'k на строку и вуаля! Производительность теперь на самом деле лучше, чем карта в моем приложении!

Вот код -

[<RequireQualifiedAccess>]
module StringTrie

type Node<'v> =
    { TrieMap : Map<char, Node<'v>>
      TrieKvp : (string * 'v) option }
    member inline x.IsEmpty = x.TrieKvp.IsNone && x.TrieMap.IsEmpty

let inline make map kvp =
    { TrieMap = map
      TrieKvp = kvp }

let inline makeEmpty () : Node<'v> = make Map.empty None

let inline isEmpty (node : Node<'v>) = node.IsEmpty

let rec tryFindInternal (key : string) index node =
    if key.Length = index then
        match node.TrieKvp with
        | Some (_, value) -> Some value
        | None -> None
    else
        let optSubNode = Map.tryFind key.[index] node.TrieMap
        match optSubNode with
        | Some subNode -> tryFindInternal key (index + 1) subNode
        | None -> None

let inline tryFind (key : string) node =
    tryFindInternal key 0 node

let inline containsKey key node =
    (tryFind key node).IsSome

let rec addInternal (key : string) index value node =
    if key.Length = index then make node.TrieMap (Some (key, value))
    else
        let char = key.[index]
        let newTrie =
            match Map.tryFind char node.TrieMap with
            | Some subTrie -> subTrie
            | None -> makeEmpty ()
        let newTrie2 = addInternal key (index + 1) value newTrie
        make (Map.add char newTrie2 node.TrieMap) node.TrieKvp

let inline add key value node =
    addInternal key 0 value node

let rec addMany kvps node =
    if Seq.isEmpty kvps then node
    else
        let kvpHead = Seq.head kvps
        let kvpTail = Seq.skip 1 kvps
        let newTrie = add (fst kvpHead) (snd kvpHead) node
        addMany kvpTail newTrie

let inline ofList kvps =
    addMany kvps (makeEmpty ())

let inline ofListBy by kvps =
    let pairs = List.map by kvps
    ofList pairs

let rec foldInternal folder rev node state =
    match node.TrieKvp with
    | Some (_, value) -> folder (Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap) (List.rev rev) value
    | None -> Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap

let inline fold folder state node =
    foldInternal folder [] node state

let rec map (mapper : string -> 'v -> 'a) (node : Node<'v>) : Node<'a> =
    match node.TrieKvp with
    | Some (key, value) -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) (Some (key, mapper key value))
    | None -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) None

let inline toValueList node =
    fold (fun state _ value -> value :: state) [] node

let inline singleton (key, value) =
    add key value (makeEmpty ())

Я также создал версию, которая работает для массивов в целом, а также быстро -

[<RequireQualifiedAccess>]
module ArrayTrie

type Node<'k, 'v when 'k : comparison> =
    { TrieMap : Map<'k, Node<'k, 'v>>
      TrieKvp : ('k array * 'v) option }
    member inline x.IsEmpty = x.TrieKvp.IsNone && x.TrieMap.IsEmpty

let inline make map kvp =
    { TrieMap = map
      TrieKvp = kvp }

let inline makeEmpty () : Node<'k, 'v> = make Map.empty None

let inline isEmpty (node : Node<'k, 'v>) = node.IsEmpty

let rec tryFindInternal (key : 'k array) index node =
    if key.Length = index then
        match node.TrieKvp with
        | Some (_, value) -> Some value
        | None -> None
    else
        let optSubNode = Map.tryFind key.[index] node.TrieMap
        match optSubNode with
        | Some subNode -> tryFindInternal key (index + 1) subNode
        | None -> None

let inline tryFind (key : 'k array) node =
    tryFindInternal key 0 node

let inline containsKey key node =
    (tryFind key node).IsSome

let rec addInternal (key : 'k array) index value node =
    if key.Length = index then make node.TrieMap (Some (key, value))
    else
        let char = key.[index]
        let newTrie =
            match Map.tryFind char node.TrieMap with
            | Some subTrie -> subTrie
            | None -> makeEmpty ()
        let newTrie2 = addInternal key (index + 1) value newTrie
        make (Map.add char newTrie2 node.TrieMap) node.TrieKvp

let inline add key value node =
    addInternal key 0 value node

let rec addMany kvps node =
    if Seq.isEmpty kvps then node
    else
        let kvpHead = Seq.head kvps
        let kvpTail = Seq.skip 1 kvps
        let newTrie = add (fst kvpHead) (snd kvpHead) node
        addMany kvpTail newTrie

let inline ofList kvps =
    addMany kvps (makeEmpty ())

let inline ofListBy by kvps =
    let pairs = List.map by kvps
    ofList pairs

let rec foldInternal folder rev node state =
    match node.TrieKvp with
    | Some (_, value) -> folder (Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap) (List.rev rev) value
    | None -> Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap

let inline fold folder state node =
    foldInternal folder [] node state

let rec map (mapper : 'k array -> 'v -> 'a) (node : Node<'k, 'v>) : Node<'k, 'a> =
    match node.TrieKvp with
    | Some (key, value) -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) (Some (key, mapper key value))
    | None -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) None

let inline toValueList node =
    fold (fun state _ value -> value :: state) [] node

let inline singleton (key, value) =
    add key value (makeEmpty ())

Единственное, что остается, как кажется, что это повысит производительность, - это получить внутренний указатель на строку и inc, а не делать индексы снова и снова. Это не кажется простым в F#, но, по крайней мере, возможно для массивов в C#.

Источник

Почему бы не быть? Как насчет OCaml, там быстрее? Так как ваш Trie реализуется с точки зрения Map Я ожидаю, что это будет медленнее, чем Map по крайней мере, для некоторых входов. Это может все еще возможно превзойти Map в некоторых случаях, например, когда размер очень большой.

Кроме того, если вас интересует производительность поиска, почему бы не заморозить Trie для использования? Dictionaryузлы?

Источник
Другие вопросы по тегам