OCaml 中连接字符串运算符的复杂度是多少？

Question

OCaml 中

str_A ^ str_B

的复杂度是多少？

Answer 1

是

O(n)

。这是函数的源代码：

let ( ^ ) s1 s2 =
  let l1 = string_length s1 and l2 = string_length s2 in
  let s = bytes_create (l1 + l2) in
  string_blit s1 0 s 0 l1;
  string_blit s2 0 s l1 l2;
  bytes_unsafe_to_string s

该函数将两个字符串的长度相加，使用该长度分配一个新的缓冲区，然后将两个输入字符串复制到其中。

在某些语言中，运行时会优化重复的字符串连接（例如几个 JavaScript 实现），但我不相信 OCaml 是基于 这个基准测试。