[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