Кто-нибудь имеет или знает постоянный префикс три в F#?

Question

Производительность F# и Map и Set довольно не хватает для моего конкретного приложения. Кажется, хороший префикс tree увеличит производительность моего интерпретатора, особенно с точки зрения поиска символов по имени. Единственное предостережение заключается в том, что он должен быть высокоэффективным для операций добавления и поиска (особенно когда ключи являются строками) и неизменным для постоянства (что означает неразрушающие обновления).

Если такого зверя нет, справочная реализация от OCaml или Haskell поможет мне начать работу с ним.

Спасибо, очень любезно!

Answer 1

Чтобы закрыть эту ветку (см. Комментарии к вопросу):

Реализация Haskell

Реализация OCaml

Answer 2

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

Ваши квалификаторы "высокоэффективный" и "неизменный для постоянства" являются взаимоисключающими. Постоянные структуры данных (как правило) по своей природе очень неэффективны, часто более чем в 10 раз медленнее, чем обязательные структуры данных.

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

Я опубликовал статью о таблицах символов здесь.

Answer 3

Итак, я просто портировал один из OCaml. К сожалению, он работает медленнее, чем стандартная карта с точки зрения tryFind. Я спрашиваю, почему в этой теме - Почему мой поиск в 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 ())