如何在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

使用字符串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

你正在做的是每次创建一个新的字符串并复制旧的值.在字符串表示为字符数组的任何语言中都非常标准.挂断发生的原因是你为每个节点做了这么多次(没有针对多个^调用的优化)!至于缓冲区,它将创建一个巨大的字符串,并在数据结构管理下不断填充它,

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