performance - 如何在Ocaml中快速将树形结构打印成字符串？

假设我在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解决方案吗？

最佳答案

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