3

为了学习的目的，我试图想出一个字符串替换函数，这就是我现在所拥有的：

let string_replace where what replacement =
  let wlength = (String.length what - 1) in
  let length = (String.length where - 1) in
  let rec loop i shift =
    let [shift, i] =
      if wlength == shift then
        (String.blit replacement 0 where (i - wlength) (wlength + 1); [0, i])
      else if (String.get where i == String.get what shift) then
        [shift + 1, i]
      else [0, i - shift]
    in if i < length then loop (i + 1) shift
  in loop 0 0; where;;

现在，这里有一个测试：http ://raid6.com.au/~onlyjob/posts/arena/所以我想看看我相对而言做得如何。而且，在这里，我编写了测试：

let test =
  let initial = "abcdefgh" ^ "efghefgh" in
  let initial_time = Sys.time() in
  let initial_length = String.length initial in
  let imax = (1024 / (String.length initial)) * 1024 * 4 in
  let rec loop s i =
    if i < imax then
      let ns = string_replace (s ^ initial) "efgh" "____" in
      let sl = initial_length * i in
      if (sl mod 1024) * 256 == 0 then
        Printf.printf "%f s | %d Kb |\n" (Sys.time() -. initial_time) (sl / 1024);
      loop ns (i + 1)
  in loop initial 0;;
test;;

我试图尽可能地关注 JavaScript 测试，以便能够比较结果（我在这里做了一些格式化，也让你不用搜索）：

function test() {
    var str = "abcdefgh" + "efghefgh",
    imax = 1024 / str.length * 1024 * 4,
    time = new Date(), gstr = "", i = 0, lngth;

    console.log("exec.tm.sec\tstr.length");

    while (i++ < imax + 1000) {
        gstr += str;
        gstr = gstr.replace(/efgh/g, "____");
        lngth = str.length * i;
        if (lngth % 1024 * 256 === 0) {
            var curdate = new Date();
            console.log((curdate.getTime() - time.getTime()) / 1000 +
                        "sec\t\t" + lngth / 1024 + "kb");
        }
    }
}

这是我得到的结果......

| JavaScript | OCaml        | String size |
|------------+--------------+-------------|
| 0.78 s     | 14.576784 s  | 256 Kb      |
| 3.266 s    | 58.468111 s  | 512 Kb      |
| 7.618 s    | 132.954788 s | 768 Kb      |
| 13.849 s   | 238.793697 s | 1024 Kb     |
| 46.243 s   | 379.175356 s | 1280 Kb     |
| 86.046 s   | 550.838260 s | 1536 Kb     |

所以，我的问题是：我的字符串替换功能有什么特别的问题吗？或者这个速度是可以预期的？我已经用ocamlopt.

这是我的另一个尝试：

let string_index_of where what =
  let length = (String.length where - 1) in
  let pattern = (1 lsl (String.length what + 1)) - 1 in
  let rec loop i j mask =
    if i == length + 1 then (-1)
    else if mask == pattern then i - j
    else if (where.[i]) == (what.[j]) then
      loop (i + 1) (j + 1) ((mask lsl 1) lor 1)
    else loop (i + 1 - j) 0 1
  in loop 0 0 1;;

let test =
  let initial = "abcdefgh" ^ "efghefgh" in
  let replacement = "____" in
  let replacement_length = String.length replacement in
  let initial_time = Sys.time() in
  let initial_length = String.length initial in
  let imax = (1024 / (String.length initial)) * 1024 * 4 in
  let rec loop s i =
    if i < imax then
      let concatenated = s ^ "efgh" in
      let sl = initial_length * i in
      let rec replace_loop st =
        let index = string_index_of st "efgh" in
        if index >= 0 then
          ((String.blit replacement 0 st index replacement_length);
           replace_loop st)
      in replace_loop concatenated;
      if sl mod (1024 * 256) == 0 then
        Printf.printf "%f s | %d Kb |\n" (Sys.time() -. initial_time) (sl / 1024);
      loop concatenated (i + 1)
  in loop initial 0;;

test;;

我还制作了一个更大的表格（包括一些其他语言进行比较）：

| JavaScript V8 | ocamlopt     | ocamlopt bitup | SBCL      | C gcc 4 -O3 | String size |
|---------------+--------------+----------------+-----------+-------------+-------------|
| 0.78 s        | 14.576784 s  | 4.615298 s     | 17.463 s  | 1 s         | 256 Kb      |
| 3.266 s       | 58.468111 s  | 18.474191 s    | 68.484 s  | 4 s         | 512 Kb      |
| 7.618 s       | 132.954788 s | 41.673664 s    | 153.99 s  | 10 s        | 768 Kb      |
| 13.849 s      | 238.793697 s | 74.652651 s    | 275.204 s | 17 s        | 1024 Kb     |
| 46.243 s      | 379.175356 s | 116.517287 s   | 431.768 s | 27 s        | 1280 Kb     |
| 86.046 s      | 550.838260 s | 166.662663 s   | 624.559 s | 38 s        | 1536 Kb     |

我仍然希望能做得更好。

4

2 回答 2

3

您的字符串搜索的复杂性很差，您应该尝试更有效的字符串搜索算法（这里是 list，我推荐KMP）

您似乎是 OCaml 的新手，因此与您习惯的语言有一些不同之处：

  • 测试结构相等的运算符是=而不是==测试物理相等的运算符（因为int没有区别，但它会在其他类型上给您带来一些麻烦）。
  • 一个元组是用(and创建的)，not [and ]which 是用于列表的，所以 [shift, i]是一个包含一个元素的列表，它是一对。而且我猜 Ocaml 抱怨这种非详尽的模式匹配。
  • String.get s i可以写s.[i]。
于 2013-07-12T18:25:54.783 回答
2

我发现很难匹配 Javascript 性能，大多数引擎 (js) 使用绳索作为字符串的内部数据结构 ( https://en.wikipedia.org/wiki/Rope_%28data_structure%29 )。

因此，每次您执行子字符串、concat 或任何应该创建新字符串（或在内部调用）的函数时，ocaml 都会构造一个新字符串，而 javascript 使用绳索来引用前一个字符串。

如果您想查看它，请在每次使用 create 时检查：（https://github.com/ocaml/ocaml/blob/trunk/stdlib/string.ml）。我想向您展示 V8 如何优化它重用字符串块，但不容易找到它，所以将它作为练习给您。

希望它有助于理解差异以及为什么 javscript 在不需要处理太多绳索时仍然比 C 表现更好。

于 2013-07-13T03:34:37.980 回答