StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Did you try using simple datastructure first before jumping on the sophisticated ones?</p> <p>On my machine, the following code is only 4x slower than you C++ version (note that I made the minimal changes to use an Array as the cache, and a list to accumulate results; you could use the array get/set syntactic sugar):</p> <pre><code>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 </code></pre> <p>(4x slower: it takes 4s to compute the 10_000_000 first primes, vs. 1s for g++ -O1 or -O2 on your code)</p> <p>Realizing that the efficiency of your bitvector solution probably comes from the economic memory layout, I changed the code to use strings instead of arrays:</p> <pre><code>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 </code></pre> <p>This now takes only 2s, which makes it 2x slower than your C++ solution.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload