Ocamlで文字列にツリー構造を高速に印刷する方法は？

Question

私はOCamlの "ツリー"形式の数式を持っていると仮定します。

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

まあ、これは非常に簡素化の定義ですが、それが問題を記述するだけで十分です。それは、このような代数型として表されます。

Plus (Number i, Number j)が(+ i j)になるように、それを逆ポーランド表記の文字列に変換したいと考えています。簡単な実装は

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^")") 

だろう。しかし事は、それは（大きな木の深さを持っている）、いくつかの入力に信じられないほど遅いだということです。例えば、この入力は私のマシンで5秒間動作します：それはyが長い文字列である文字列の連結x^yを、思わ

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 

を、パフォーマンス上の問題があります。実際、"(+"^s^" "^p^")"の式をs^pと置き換えると、それはとなります。

連結の代わりにprintfを使用してもそれ以上の高速化はありません。 Cに変換すると助けになるかもしれませんが、OCamlソリューションはありませんか？

Answer 1

文字列Bufferを使用します。

^が何をやっている

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 

、と定義され、新しい文字列を毎回作成し、文字列は文字配列として表現されている任意の言語で。ほとんど標準で古い値をコピーです。ハングアップは、各ノードに対してこれを4回実行しているために発生します（複数の^コールの最適化はありません）！バッファーとしては、それはあなたが1に初期バッファサイズを作成することを決定した場合でも、resize関数はサイズを調整します

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

、巨大な文字列を作成し、継続的なデータ構造で管理されるようにそれを記入します再配分の回数を制限するような形で行われます。たとえば、add_string関数は配列のサイズをlen*2^(n+p-len)で増やします。nは新しい文字列の長さ、pは位置、lenは元のバッファの長さです - バッファが文字列をサポートできない場合のみ、もちろん。したがって、バッファのサイズは指数関数的に増加し、処理が進むにつれて再割り当てはほとんどありません。もちろん、最初のバッファを妥当なものに設定することが最善ですが、必ずしもそうする必要はありません。

新しいconvert機能は、はるかに詳細な見ていないでしょう。

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 ")")