So, I'm doing the whole Euler thing, and I'm writing a function for
finding primes using wheel factorization in combination with the Sieve
of Eratosthenes.
The algorithm is correct, but very slow. I've managed to isolate the
part that's having unexpectedly bad performance.
I just can't see why the last of these four expressions is so slow.
The only overhead it ought to have is a single "if" statement. I am
beginning to think there's something about the implementation of
filter that I'm missing... Any help would be greatly appreciated.
The code below uses only 2 functions... "wheelfactor?" returns a
boolean if the number is a good candidate for a prime by wheel
factorization, "eratosthenes" checks a given number against a sieve.
For the purposes of this demonstration I've defined the sieve to
merely be the first 1000 primes - so the answers returned here aren't
necessarily correct, but the performance factors ought to be about the
same. I have ran all the benchmarks multiple times against a warmed-up
JVM, so that's not the issue.
;;See how long wheelfactor? takes to run over 100k
(time (dorun (filter wheelfactor? (range 1 100000))))
;;30 milliseconds
;;See how long a simple eratosthenes takes to run over 100k
(time (dorun (filter #(eratosthenes % sieve) (range 1 100000))))
;;13 seconds
;;See how many numbers < 100k are potential primes?
(count (filter wheelfactor? (range 1 100000)))
;;26687
;;See how long it takes to run eratosthenes
;;to evaluate 26687 large numbers:
(time (dorun (filter #(eratosthenes % sieve) (range (- 100000 26687)
100000))))
;;3 seconds
;;See how long it takes to run a combination
;;I expect ~3 seconds, from the previous tests
(time (dorun (filter #(if (wheelfactor? %)
(eratosthenes % sieve))
(range 1 100000))))
;;13 seconds!?
;;But I put a trace in eratosthenes and it still only runs 26687
times!?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
