代码之家 › 专栏 › 技术社区 › P Shved

如何在Ocaml中将树结构快速打印成字符串?

ocaml string performance

P Shved · 技术社区 · 14 年前

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

1 回复 | 直到 13 年前

nlucaroni 14 年前

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