另一个综合基准:Sieve of Eratosthenes

C++

#include <vector>
#include <cmath>

void find_primes(int n, std::vector<int>& out)
{
   std::vector<bool> is_prime(n + 1, true);
   int last = sqrt(n);
   for (int i = 2; i <= last; ++i)
   {
      if (is_prime[i])
      {
         for (int j = i * i; j <= n; j += i)
         {
            is_prime[j] = false;
         }
      }
   }

   for (unsigned i = 2; i < is_prime.size(); ++i)
   {
      if (is_prime[i])
      {
         out.push_back(i);
      }
   }
}

OCaml(使用 Jane Street's Core 和 Res 库)

open Core.Std
module Bits = Res.Bits
module Vect = Res.Array

let find_primes n =
  let is_prime = Bits.make (n + 1) true in
  let last = float n |! sqrt |! Float.iround_exn ~dir:`Zero in
  for i = 2 to last do
    if not (Bits.get is_prime i) then () else begin
      let j = ref (i * i) in
      while !j <= n; do
        Bits.set is_prime !j false;
        j := !j + i;
      done;
    end;
  done;
  let ar = Vect.empty () in
  for i = 2 to n do
    if Bits.get is_prime i then Vect.add_one ar i else ()
  done;
  ar

令我惊讶的是 OCaml 版本(原生)比 C++ 慢了大约 13 倍。我用 Core_extended.Bitarray 替换了 Res.Bits，但速度变慢了约 18 倍。为什么这么慢？ OCaml 不为位操作提供快速操作吗？是否有任何替代的快速实现位数组？

需要说明的是:我来自 C++ 世界，并且将 OCaml 视为编写性能关键代码的可能替代方案。事实上，我对这样的结果有点害怕。

编辑:

分析结果

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 50.81      1.26     1.26                             camlRes__pos_1113
  9.72      1.50     0.24                             camlRes__unsafe_get_1117
  6.68      1.66     0.17                             camlRes__unsafe_set_1122
  6.28      1.82     0.16                             camlNopres_impl__set_1054
  6.07      1.97     0.15                             camlNopres_impl__get_1051
  5.47      2.10     0.14 47786824     0.00     0.00  caml_apply3
  3.64      2.19     0.09 22106943     0.00     0.00  caml_apply2
  2.43      2.25     0.06   817003     0.00     0.00  caml_oldify_one
  2.02      2.30     0.05        1    50.00   265.14  camlPrimes__find_primes_64139
  1.21      2.33     0.03                             camlRes__unsafe_get_1041
...

最佳答案

在开始使用复杂的数据结构之前，您是否尝试过先使用简单的数据结构？

在我的机器上，下面的代码只比你的 C++ 版本慢 4 倍(请注意，我做了最小的改动，使用一个数组作为缓存，并使用一个列表来累积结果；你可以使用数组 get/set 语法糖):

let find_primes n =
  let is_prime = Array.make (n + 1) true in
  let last = int_of_float (sqrt (float n)) in
  for i = 2 to last do
    if not (Array.get is_prime i) then () else begin
      let j = ref (i * i) in
      while !j <= n; do
        Array.set is_prime !j false;
        j := !j + i;
      done;
    end;
  done;
  let ar = ref [] in
  for i = 2 to n do
    if Array.get is_prime i then ar := i :: !ar else ()
  done;
  ar

(慢 4 倍:计算 10_000_000 个第一个素数需要 4 秒，而 1 秒 用于代码中的 g++ -O1 或 -O2)

意识到你的 bitvector 解决方案的效率可能 来自经济内存布局，我更改了代码以使用 字符串而不是数组:

let find_primes n =
  let is_prime = String.make (n + 1) '0' in
  let last = int_of_float (sqrt (float n)) in
  for i = 2 to last do
    if not (String.get is_prime i = '0') then () else begin
      let j = ref (i * i) in
      while !j <= n; do
        String.set is_prime !j '1';
        j := !j + i;
      done;
    end;
  done;
  let ar = ref [] in
  for i = 2 to n do
    if String.get is_prime i = '0' then ar := i :: !ar else ()
  done;
  ar

这现在只需要 2 秒，这使得它比你的 C++ 慢 2 倍 解决方案。

关于c++ - OCaml 中的快速位数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14731554/