[squeak-dev] Re: Generators in Smalltalk?
Levente Uzonyi
leves at elte.hu
Thu Feb 11 00:25:01 UTC 2010
On Wed, 10 Feb 2010, Enrico Spinielli wrote:
> SICP to the rescue
> http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2
Well, this is not efficient. It states that it implements the sieve of
Eratosthenes, but it uses division... A smalltalk equivalent with
generators would look like this (according to my minimal lisp knowledge):
primeGenerator := Generator on: [ :yield |
| primes i |
yield value: 2.
primes := OrderedCollection with: 2.
i := 3.
[
(primes noneSatisfy: [ :prime | i \\ prime = 0 ])
ifTrue: [
primes add: i.
yield value: i ].
i := i + 2.
true ] whileTrue ].
There are 9592 primes that are smaller than 100000.
[ 1 to: 9592 do: [ :i | primeGenerator next ] ] timeToRun. "===> 13061"
Compare this with a real sieve (which doesn't use division at all):
[ Integer primesUpTo: 100000 do: #yourself ] timeToRun "===> 13"
1000x faster.
Levente
>
> Probably inspiring in the context of this thread.
> Bye
> Enrico
>
> On Wed, Feb 10, 2010 at 8:16 AM, Levente Uzonyi <leves at elte.hu> wrote:
>
>> On Tue, 9 Feb 2010, Andreas Raab wrote:
>>
>> Colin Putney wrote:
>>>
>>>> Also, Stephen Pair posted an implementation here in December:
>>>> http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
>>>>
>>>
>>> Brilliant! That's the ticket! Once I got down the right path it's even
>>> simpler than that. I put a version of Generator into the inbox for people to
>>> play with and give feedback. With 5 methods total you get to do fun stuff
>>> like:
>>>
>>> | gen max |
>>> max := 10000000.
>>> gen := Generator on:[:yield| Integer primesUpTo: max do: yield].
>>> 'Computing primes' displayProgressAt: Sensor cursorPoint
>>> from: 1 to: max during:[:bar| | prime |
>>> [prime := gen next] whileNotNil:[bar value: prime].
>>> ].
>>>
>>> I think we should add support for Generators. They are so incredibly
>>> useful where you have complex operations that you don't want to spend the
>>> upfront effort on to compute everything (like primes) before you can do some
>>> work with the results.
>>>
>>
>> I wonder how can you use generators to generate primes efficiently _and_ on
>> the fly.
>>
>>
>> Levente
>>
>>
>>> Cheers,
>>> - Andreas
>>>
>>>
>>>
>>
>
>
> --
> Enrico Spinielli
> "Do Androids dream of electric sheep?"? Philip K. Dick
> "Hear and forget; see and remember;do and understand."?Mitchel Resnick
>
More information about the Squeak-dev
mailing list
|