[plt-scheme] Unreasonably slow
Problem solved. Alex is using Python's itertools library, which
brought quasi-functional programming to Python -- in the form of a C
library. If you look at his code (forwarded w/o permission), you'll
see that the Python contribution is a while-true loop, the rest are
two or three calls to C functions. I suspect that an equivalent
formulation in PLT would perform at the same level.
Thanks -- Matthias
On Oct 29, 2008, at 11:37 AM, Alex Rozenshteyn wrote:
> On Oct 29, 2008, at 11:16 AM, Alex Rozenshteyn wrote:
>
> import itertools
>
> def iter_primes():
> # an iterator of all numbers between 2 and +infinity
> numbers = itertools.count(2)
> # generate primes forever
> while True:
> # get the first number from the iterator (always a prime)
> prime = numbers.next()
> yield prime
>
> # remove all numbers from the (infinite) iterator that are
> # divisible by the prime we just generated
> numbers = itertools.ifilter(prime.__rmod__, numbers)
> gen=iter_primes()
> print [gen.next() for i in xrange(10001)][-1]
>
>
> runs with this time:
>
> real 0m7.990s
> user 0m7.928s
> sys 0m0.028s
>
> On Wed, Oct 29, 2008 at 10:48 AM, Matthias Felleisen
> <matthias at ccs.neu.edu> wrote:
>
> On Oct 29, 2008, at 10:32 AM, Matthias Felleisen wrote:
>
>
>
> Let me confirm the following times and value on a 2G Intel mini-
> Mac, no debugging info:
>
> cpu time: 186221 real time: 187920 gc time: 81912
>
> cpu time: 28802 real time: 28877 gc time: 0
> 104743
>
>
> Since Python's generators aren't lazy and don't impose any
> overhead, I rewrote your algorithm with functions that I'd ask my
> freshmen to write (i.e., explain the sieve idea, have them code it
> up) and what I got is something that's an order of magnitude faster
> and gives the same result (I had forgotten to count from 0 so I was
> stumped for a split second).
>
> How fast is your Python solution? -- Matthias
>
>
>
>
>
>
>
>
>
> [The r5rs required seems unnecessary.]
>
> ;; ---
>
> I also spent 3 minutes trying to port this to lazy Scheme but it's
> error-highlight is so, eh, lazy that it's no fun. -- Matthias
>
>
>
>
> On Oct 29, 2008, at 9:28 AM, Alex Rozenshteyn wrote:
>
> I wrote this code for project euler problem 7:
>
> (require r5rs)
> (require srfi/41)
>
> (define stream-primes
> (let ((numbers (stream-cons 2 (stream-from 3 2)))
> (filter-stream
> (stream-lambda
> (divisor strm)
> (let ((not-div
> (lambda (dividend)
> (not (zero? (modulo dividend divisor))))))
> (stream-filter not-div strm)))))
> (stream-let
> loop
> ((strm numbers)
> (primes stream-null))
> (define prime (stream-car strm))
> (stream-append
> (stream prime)
> (loop (filter-stream prime (stream-cdr strm))
> (stream-append primes (stream prime)))))))
>
> and I ran (stream-ref stream-primes 10000)
>
> It took unreasonably long to run. Much longer than it took my
> python code (which uses python's generators, to which srfi/41's
> lazy comprehensions are as close as I can find in scheme). I'm
> curious as to whether this is an artifact of lazy comprehensions in
> scheme being slow or just my code being wrong.
>
> Thank you to anyone who takes the time to read this.
>
> --
> Alex R
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>
>
>
> --
> Alex R
>
>
>
>
> --
> Alex R