2

私の特定のアプリケーションでは、F# の Map と Set のパフォーマンスがかなり不足しています。良い接頭辞 trie は、特に名前によるシンボル検索に関して、インタープリターのパフォーマンスをかなり向上させるようです。唯一の注意点は、追加操作と検索操作 (特にキーが文字列の場合) に対して非常に効率的であり、永続性 (非破壊的な更新を意味する) に対して不変でなければならないということです。

そのようなビーストが利用できない場合は、OCaml または Haskell からの参照実装を使用して開始することができます。

よろしくお願いします！

4

3 に答える 3

3

このスレッドを閉じるには (質問に関するコメントを参照):

Haskell 実装

OCaml の実装

于 2012-07-09T16:37:41.103 に答える
2

良い接頭辞 trie は、特に名前によるシンボル検索に関して、インタープリターのパフォーマンスをかなり向上させるようです。唯一の注意点は、追加操作と検索操作 (特にキーが文字列の場合) に対して非常に効率的であり、永続性 (非破壊的な更新を意味する) に対して不変でなければならないということです。

あなたの修飾子「非常に効率的」と「持続性のために不変」は相互に排他的です。永続的なデータ構造は (通常) 本質的に非常に非効率的であり、多くの場合、命令型のデータ構造よりも 10 倍以上遅くなります。

シンボルであるキーを持つ高速な辞書が必要な場合は、シンボル テーブルが必要です。パブリック API はシンボルを文字列として使用しますが、これらはハッシュ テーブルを介して内部的に小さな正の整数に変換され、元に戻されます。キーとしてシンボルを持つ辞書は、シンボルを表すために使用される整数によってインデックス付けされた配列として表すことができます。

ここでシンボル テーブルに関する記事を公開しました。

于 2012-07-15T11:41:36.730 に答える
0

というわけで、OCaml から移植したところです。残念ながら、tryFind に関しては、標準の Map よりも遅くなります。このスレッドで理由を尋ねています -なぜ私の Trie ルックアップは標準の 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 =
    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 ())
于 2012-07-13T13:44:37.623 に答える