对于我的特定应用程序,F# 的 Map 和 Set 的性能相当欠缺。似乎一个不错的前缀特里树会大大提高我的解释器的性能,尤其是在按名称查找符号方面。唯一需要注意的是,它必须对添加和查找操作非常有效(尤其是当键是字符串时),并且对于持久性是不可变的(意味着非破坏性更新)。
如果没有这样的野兽可用,OCaml 或 Haskell 的参考实现将帮助我开始使用。
非常感谢!
对于我的特定应用程序,F# 的 Map 和 Set 的性能相当欠缺。似乎一个不错的前缀特里树会大大提高我的解释器的性能,尤其是在按名称查找符号方面。唯一需要注意的是,它必须对添加和查找操作非常有效(尤其是当键是字符串时),并且对于持久性是不可变的(意味着非破坏性更新)。
如果没有这样的野兽可用,OCaml 或 Haskell 的参考实现将帮助我开始使用。
非常感谢!
似乎一个不错的前缀特里树会大大提高我的解释器的性能,尤其是在按名称查找符号方面。唯一需要注意的是,它必须对添加和查找操作非常有效(尤其是当键是字符串时),并且对于持久性是不可变的(意味着非破坏性更新)。
您的限定词“高效”和“持久不变”是相互排斥的。持久性数据结构(通常)本质上非常低效,通常比命令式数据结构慢 10 倍以上。
如果您想要一个带有符号键的快速字典,那么您需要一个符号表。您的公共 API 使用符号作为字符串,但这些在内部通过哈希表转换为小的正整数并返回。然后可以将带有符号作为键的字典表示为由用于表示符号的整数索引的数组。
我在这里发表了一篇关于符号表的文章。
所以,我只是从 OCaml 移植了一个。不幸的是,它在 tryFind 方面的运行速度比标准 Map 慢。我在这个线程中问为什么 -为什么我的 Trie 查找比标准 F# Map 的慢?
这是代码 -
[<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 =
match key with
| [] ->
match node.TrieKvp with
| Some (_, value) -> Some value
| None -> None
| keyHead :: keyTail ->
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 =
match key with
| [] -> make node.TrieMap (Some (key, value))
| keyHead :: keyTail ->
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 ())