Wie drucke ich eine Baumstruktur in Ocaml schnell?

Question

Angenommen, ich habe einen mathematischen Ausdruck in einer "Baum" -Form in OCaml. Es ist, als ein algebraischer Typ wie folgt dargestellt:

type expr = 
    Number of int 
    |Plus of expr*expr 

Nun, das ein ist sehr Definition vereinfachte, aber es ist genug, um das Problem zu beschreiben.

Ich möchte es in eine umgekehrte polnische Notation umwandeln, so dass Plus (Number i, Number j)(+ i j) wird. Eine einfache Implementierung würde

let rec convert = function 
    Number i -> string_of_int i 
    |Plus (a,b) -> (let s = convert a in let p = convert b in "(+"^s^" "^p^")") 

sein Aber die Sache ist, dass es unglaublich langsam auf eine Eingabe (die einen großen Baumtiefe haben). Zum Beispiel arbeitet dieser Eingang 5 Sekunden auf meinem Rechner:

let rec make_pain so_far = function 
    0 -> so_far |i -> make_pain (Plus (Number 1,so_far)) (i-1) 

let pain = make_pain (Number 1) 20000 

let converted = convert pain 

es, dass die String-Verkettung scheint x^y, wo y eine lange Reihe ist, ist das Leistungsproblem. In der Tat, wenn ich die "(+"^s^" "^p^")" Ausdruck mit nur s^p ersetzen, wird es schneller viel.

Die Verwendung von printf anstelle der Verkettung macht es nicht schneller. Konvertieren in C könnte helfen, aber gibt es keine OCaml-Lösung?

Answer 1

Verwenden Sie eine Zeichenfolge Buffer. Jedesmal, wenn eine neue Zeichenfolge wird das Erstellen und Kopieren der alten Werte in. So ziemlich Standard in jeder Sprache

^ als definierte

let (^) s1 s2 = 
    let l1 = string_length s1 and l2 = string_length s2 in 
    let s = string_create (l1 + l2) in 
    string_blit s1 0 s 0 l1; 
    string_blit s2 0 s l1 l2; 
    s 

Was Sie tun, wo Strings als Zeichen-Arrays dargestellt werden. Das Aufhängen geschieht, weil Sie dies viermal für jeden Knoten tun (es gibt keine Optimierung für mehrere ^ Aufrufe)! Wie für einen Puffer, wird es eine riesige Zeichenfolge erstellen und kontinuierlich in füllen, wie durch die Datenstruktur verwaltet,

type t = 
    {mutable buffer : string; 
    mutable position : int; 
    mutable length : int; 
    initial_buffer : string} 

Auch wenn Sie die anfängliche Puffergröße 1 erstellen entscheiden, die resize Funktion passen Sie die Größe in einer Weise, die die Anzahl der Neuzuteilungen begrenzt. Zum Beispiel wird die add_string Funktion die Größe des Arrays um len*2^(n+p-len) erhöhen, wobei n die Länge der neuen Zeichenfolge ist ist die Position und len ist die Länge des ursprünglichen Puffer - nur wenn der Puffer die Zeichenfolge nicht unterstützen kann, Na sicher. Daher wächst die Größe des Puffers exponentiell und es werden im Verlauf der Dinge nur wenige Neuzuweisungen vorgenommen. Natürlich ist es am besten, den Anfangspuffer auf etwas Vernünftiges zu setzen, aber das ist nicht notwendig.

Die neue convert Funktion würde nicht aussehen viel ausführlicher:

let rec convert buf ex = 
    let addb = Buffer.add_string buf in 
    match ex with 
    Number i -> addb (string_of_int i) 
    |Plus (a,b) -> (addb "(+ "; convert buf a; addb " "; convert buf b; addb ")")