Comment imprimer une structure arborescente en une chaîne rapide dans Ocaml?

Question

Supposons que j'ai une expression mathématique dans un formulaire "arbre" dans OCaml. Il est représenté comme un type algébrique comme ceci:

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

Eh bien, cela est une très simplifiée définition, mais il suffit de décrire le problème. Je veux le convertir en une chaîne dans une notation polonaise inverse, de sorte que Plus (Number i, Number j) devient (+ i j). Une mise en œuvre simple serait

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

Mais la chose est qu'il est incroyablement lent sur une entrée (qui ont une grande profondeur de l'arbre). Par exemple, cette entrée fonctionne 5 secondes sur ma machine:

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 

Il semble que la concaténation de chaîne x^y, où y est une longue chaîne, est le problème de performance. En effet, si je remplace l'expression "(+"^s^" "^p^")" par un simple s^p, il devient beaucoup plus vite.

L'utilisation de printf au lieu de la concaténation ne le rend pas plus rapide. La conversion en C peut aider, mais n'y a-t-il pas une solution OCaml?

Answer 1

Utilisez une chaîne Buffer.

^ est défini comme,

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 

Ce que vous faites est de créer une nouvelle chaîne à chaque fois et copier les anciennes valeurs. Assez standard dans toutes les langues où les chaînes sont représentées sous forme de tableaux de caractères. Le raccrochage se produit parce que vous faites ceci QUATRE fois pour chaque nœud (il n'y a pas d'optimisation pour plusieurs appels ^)! En ce qui concerne un tampon, il va créer une chaîne géante et remplir en permanence en tant que gérée par la structure de données,

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

Même si vous décidez de créer la taille initiale du tampon à 1, la fonction resize ajustera la taille d'une manière qui limitera le nombre de réaffectations. Par exemple, la fonction add_string augmentera la taille du tableau par len*2^(n+p-len), où n est la longueur de la nouvelle chaîne, p est la position et len est la longueur du tampon d'origine - uniquement si le tampon ne peut pas supporter la chaîne, bien sûr. Ainsi, la taille du tampon augmente de façon exponentielle et il y aura peu de réaffectations au fur et à mesure que les choses progressent. Bien sûr, il vaut mieux définir le tampon initial sur quelque chose de raisonnable, mais ce n'est pas nécessaire.

La nouvelle fonction convert ne regarderais pas beaucoup plus bavard:

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