4

所以，我刚刚从 OCaml 移植了 Trie。不幸的是，它在 tryFind 方面的运行速度比标准 Map 慢。我不明白这一点 - 特里似乎应该更快。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 ())

这是 Jon Harrop 提供的性能测试，我发现它足以衡量改进 -

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

注意：如果您有更快的查找数据结构，请注意我需要一个持久数据结构。

4

3 回答 3

4

不幸的是，它在 tryFind 方面的运行速度比标准 Map 慢。我不明白这一点 - 特里似乎应该更快。

这里的快速基准表明您的尝试已经比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 来构建 aMap并且0.7在这两种情况下都将进行搜索。

但是，您的实施还有很大的改进空间。我最近写了一篇关于 F# 中优化的通用持久哈希树实现的文章，发表在此处。

您后来的评论暗示您只想使用它来映射字符串。如果是这样，将您的 trie 专门用于字符串键会更加有效。

编辑

KVB 建议我详细说明“改进空间”，所以这里有一些反馈：

  • 谨慎使用inline作为优化，并且仅在引人注目的性能测量的基础上使用。
  • 创建empty一个值而不是一个函数。
  • List.head尽可能避免List.tail。请改用模式匹配。
  • 尽可能避免通用性（例如，在这种情况下，字符串键的硬编码）。
于 2012-07-14T10:36:58.883 回答
4

好吧，经过更多思考，我假设性能的真正差异在于使用列表作为键而不是字符串。字符串（和数组）具有更好的缓存一致性。所以，我将键从'k 列表更改为字符串，瞧！性能现在实际上比我的应用程序中的 Map 更好！

这是代码 -

[<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# 中的数组来说似乎是可能的。

于 2012-07-15T01:00:04.107 回答
2

为什么不呢？OCaml 怎么样，那里更快吗？由于您Trie的实施方式是Map我希望它Map至少比某些输入慢。在某些情况下，它可能仍然可以胜过Map，例如当尺寸非常大时。

此外，如果您的主要兴趣是查找性能，为什么不冻结您的 Trie 以使用Dictionary-based 节点？

于 2012-07-13T14:17:32.220 回答