[plt-scheme] Unreasonably slow
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