首页 文章

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

提问于
浏览 次
6

假设我在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^")")

但问题是它在某些输入（具有很大的树深度）上是 incredibly slow . 例如，此输入在我的机器上工作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^")" 表达式，它会变得更快 much .

使用 printf 而不是连接还没有OCaml解决方案吗？

performance string ocaml

1 回答

  • 9

    使用字符串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 是原始缓冲区的长度 - 只有缓冲区不能支持字符串，当然 . 因此，缓冲区的大小呈指数级增长，随着事情的发展，重新分配的次数也会很少 . 当然，它必须是's best to set the initial buffer to something reasonable, but it isn' t .

    新的 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 ")")
    回复于

相关问题