[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