Cómo imprimir rápidamente una estructura de árbol en una cadena en Ocaml?

Question

Supongamos que tengo una expresión matemática en forma de "árbol" en OCaml. Está representado como un tipo algebraica de esta manera:

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

Pues bien, este es un muy definición simplificada, pero es suficiente para describir el problema.

Quiero convertirlo en una cadena en una notación polaca inversa, de modo que Plus (Number i, Number j) se convierta en (+ i j). Una aplicación sencilla sería

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

Pero la cosa es que es increíblemente lento en alguna entrada (que tiene una profundidad de árbol grande). Por ejemplo, esta entrada 5 segundos funciona en mi máquina:

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 

Parece que x^y concatenación de cadenas, donde y es una cadena larga, es el problema de rendimiento. De hecho, si reemplazo la expresión "(+"^s^" "^p^")" con mera s^p, se convierte en mucho más más rápido.

El uso de printf en lugar de concatenación no lo hace más rápido. Convertir a C podría ayudar, ¿pero no hay una solución OCaml?

Answer 1

Utilice una cadena Buffer.

^ se define como,

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 

Lo que está haciendo es crear una nueva cadena cada vez y copiar los viejos valores en. Más o menos estándar en cualquier idioma, donde las cadenas se representan como matrices de caracteres. El hangup ocurre porque estás haciendo CUATRO veces para cada nodo (¡no hay una optimización para múltiples llamadas ^)! En cuanto a un tampón, se creará una cadena gigante y continuamente rellenarlo como gestionado por la estructura de datos,

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

Incluso si se decide crear el tamaño del búfer inicial a 1, la función resize ajustará el tamaño de una manera que limitará el número de reasignaciones. Por ejemplo, la función add_string aumentará el tamaño de la matriz en len*2^(n+p-len), donde n es la longitud de la nueva cadena, p es la posición y len es la longitud del búfer original, solo si el búfer no puede soportar la cadena, por supuesto. Por lo tanto, el tamaño del buffer crece exponencialmente y habrá pocas reasignaciones a medida que avancen las cosas. Por supuesto, es mejor configurar el búfer inicial a algo razonable, pero no es necesario.

La nueva función convert no se ven mucho más prolija:

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