Как быстро распечатать древовидную структуру в строку в 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 секунд:

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

Кажется, что конкатенация строк x^y, где y - длинная строка, является проблемой производительности.Действительно, если я заменим выражение "(+"^s^" "^p^")" простым s^p, оно станет на намного быстрее.

Использование printf вместо конкатенации не сделает его быстрее.Преобразование в C может помочь, но разве нет решения OCaml?

Answer 1

Использовать строку Буфер .

^ определяется как,

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

То, что вы делаете, это каждый раз создаете новую строку и копируете старые значения. Практически стандартно для любого языка, где строки представлены в виде символьных массивов. Зависание происходит из-за того, что вы делаете это ЧЕТЫРЕ раза для каждого узла (нет оптимизации для нескольких вызовов ^)! Что касается буфера, он создаст гигантскую строку и будет непрерывно заполнять ее, как управляется структурой данных,

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

Даже если вы решите создать начальный размер буфера равным 1, функция resize отрегулирует размер таким образом, чтобы ограничить количество перераспределений. Например, функция 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 ")")