performance - OCaml 中的高效求和

Question

请注意，我几乎是 OCaml 的新手。为了学习一点，并测试它的性能，我尝试使用 Leibniz series 实现一个近似 Pi 的模块。 .

我的第一次尝试导致堆栈溢出(实际错误，不是这个站点)。从 Haskell 知道这可能来自太多的“thunk”，或者 promise 计算某些东西，在递归加数时，我寻找了一些方法来保持最后一个结果，同时与下一个结果相加。我发现了以下 sum 的尾递归实现和 map在 OCaml 类(class)的笔记中，here和 here ，并期望编译器产生有效的结果。

然而，生成的可执行文件，用 ocamlopt 编译。 , 比使用 clang++ 编译的 C++ 版本慢得多.这段代码是否尽可能高效？我缺少一些优化标志吗？

我的完整代码是:

let (--) i j =
  let rec aux n acc =
    if n < i then acc else aux (n-1) (n :: acc)
    in aux j [];;


let sum_list_tr l =
  let rec helper a l = match l with
    | [] -> a
    | h :: t -> helper (a +. h) t
  in helper 0. l


let rec tailmap f l a = match l with
  | [] -> a
  | h :: t -> tailmap f t (f h :: a);;


let rev l =
    let rec helper l a = match l with
      | [] -> a
      | h :: t -> helper t (h :: a)
    in helper l [];;


let efficient_map f l = rev (tailmap f l []);;


let summand n =
  let m = float_of_int n
  in (-1.) ** m /. (2. *. m +. 1.);;


let pi_approx n =
  4. *. sum_list_tr (efficient_map summand (0 -- n));;


let n = int_of_string Sys.argv.(1);;
Printf.printf "%F\n" (pi_approx n);;

仅供引用，以下是我机器上测量的时间:

❯❯❯ time ocaml/main 10000000
3.14159275359
ocaml/main 10000000  3,33s user 0,30s system 99% cpu 3,625 total

❯❯❯ time cpp/main 10000000
3.14159
cpp/main 10000000  0,17s user 0,00s system 99% cpu 0,174 total

为了完整起见，让我声明第一个辅助函数，相当于 Python 的 range , 来了 from this SO thread ，并且这是使用 OCaml 版本 4.01.0 运行的，通过 MacPorts 在 Darwin 13.1.0 上安装。

Answer 1

正如我在评论中指出的，OCaml 的 float是盒装的，这使得 OCaml 与 Clang 相比处于劣势。

但是，我可能会注意到在 Haskell 之后尝试 OCaml 的另一个典型的粗糙边缘:
如果我看到你的程序在做什么，你正在创建一个东西列表，然后在该列表上映射一个函数，最后将它折叠成一个结果。

在 Haskell 中，您或多或少会期望这样的程序会自动“deforested ” 在编译时，因此生成的代码是手头任务的有效实现。

在 OCaml 中，函数可能具有副作用，特别是传递给高阶函数(如 map 和 fold)的函数，这意味着编译器自动去森林化将更加困难。程序员必须手动完成。

换句话说:停止构建巨大的短期数据结构，例如 0 -- n和 (efficient_map summand (0 -- n)) .当你的程序决定处理一个新的求和时，让它在一次通过中完成它想做的所有事情。您可以将其视为应用 Wadler 文章中的原则的练习(同样，手动，因为由于各种原因，尽管您的程序是纯程序，但编译器不会为您执行此操作)。

以下是一些结果:

$ ocamlopt v2.ml$ time ./a.out 10000003.14159165359real    0m0.020suser    0m0.013ssys     0m0.003s$ ocamlopt v1.ml$ time ./a.out 10000003.14159365359real    0m0.238suser    0m0.204ssys     0m0.029s

v1.ml is your version. v2.ml is what you might consider an idiomatic OCaml version:

let rec q_pi_approx p n acc =
  if n = p
  then acc
  else q_pi_approx (succ p) n (acc +. (summand p))

let n = int_of_string Sys.argv.(1);;

Printf.printf "%F\n" (4. *. (q_pi_approx 0 n 0.));;

(从您的代码中重用 summand)

从最后一项到第一项而不是从第一项到最后一项可能更准确。这与您的问题正交，但您可以将其视为修改已强制尾递归的函数的练习。此外， (-1.) ** m summand 中的表达式由编译器映射到对 pow() 的调用。主机上的函数，即 a bag of hurt你可能想避免。