Ağaç yapısını Ocaml'de hızlı bir dize nasıl yazdırılır?

Question

"Benim" matematiksel bir ifadem var OCaml.

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

Eh, bu çok tanımını basitleştirilmiş bir , ancak sorunu açıklamak için yeterli: Şöyle bir cebirsel türü olarak temsil edilir.

Ben Plus (Number i, Number j)(+ i j) olur böylece bir ters cila gösterimde bir dizeye dönüştürmek istiyorum. Bir basit uygulama

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

olurdu Ama şey (büyük ağaç derinliğini var) bazı girişinde inanılmaz yavaş olmasıdır. ,

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 

O y uzun dizesi olduğunu dize birleştirme x^y, görünüyor performans sorunudur: Örneğin, bu girdi benim makinede 5 saniye çalışır. Ben sadece s^p ile "(+"^s^" "^p^")" ifadeyi değiştirmek eğer Nitekim, bu çok daha hızlı hale gelir.

daha hızlı yapmaz yerine birleştirme printf kullanma. C'ye dönüştürme yardımcı olabilir, ancak bir OCaml çözümü yok mu?

Answer 1

kullanın bir dize Buffer.

^

, olarak tanımlanır

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 

Ne yeni dize her zaman yaratmak ve eski değerleri kopyalıyor yapıyoruz. Hemen hemen standardını dizeleri karakter dizileri olarak temsil edilir herhangi bir dilde. Bu kapanış, her düğüm için bu DÖRT sürelerini yaptığınız için gerçekleşir (birden çok ^ çağrısı için bir optimizasyon yoktur)! Eğer 1 başlangıç ​​tampon boyutunu oluşturmaya karar bile bir tampon gelince, o resize işlev boyutuna ayarlayacaktır,

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

dev dize oluşturmak ve sürekli olarak veri yapısı tarafından yönetilen olarak dolduracaktır Yeniden tahsislerin sayısını sınırlayacak şekilde. Örneğin, add_string işlevi dizinin boyutunu len*2^(n+p-len), n yeni dizenin uzunluğunda, p konumunu ve len arabellek dizeyi desteklemiyorsa, yalnızca orijinal arabellek uzunluğunu artırır. tabii ki. Böylece, tamponun boyutu katlanarak büyür ve işler ilerledikçe çok az yeniden tahsis olacaktır. Tabii ki, başlangıç ​​arabelleğini makul bir şeye ayarlamak en iyisidir, ama gerekli değildir.

yeni convert fonksiyonu çok daha ayrıntılı bakmak olmaz:

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