thanks Nicolas could you have a look at the prime number generation issue? Stef
On Feb 2, 2012, at 8:30 PM, Nicolas Cellier wrote: > I've created http://code.google.com/p/pharo/issues/detail?id=5237 and > http://code.google.com/p/pharo/issues/detail?id=5238 > > Nicolas > > 2012/2/2 Nicolas Cellier <[email protected]>: >> Sure, but this leaves plenty of room to Andreas for improving LinkedList. >> For example, collect: has been improved, but what about select: ? >> >> { >> [(Array withAll: (1 to: 1000)) select: [:e | e even]] bench. >> [(LinkedList withAll: (1 to: 1000)) select: [:e | e even]] bench. >> }. >> -> #('7,240 per second.' '64.3 per second.') >> >> Also, tell why ((1 to: 10) as: LinkedList) isEmpty, or correct it... >> >> Your contributions are welcome, via >> http://www.pharo-project.org/community/issue-tracking >> (I hope the page is up to date). >> >> Nicolas >> >> 2012/2/2 Ben Coman <[email protected]>: >>> Henrik Johansen wrote: >>>> >>>> On Feb 2, 2012, at 10:34 AM, Andreas Haufler (scireum GmbH) wrote: >>>> >>>> >>>>> >>>>> Hi everyone, >>>>> >>>>> I'm a Pharo newbie with some knowledge about Smalltalk. Surfing through >>>>> the code base I stumbled over the implementation of LinkedList collect: - >>>>> Your're right, there is none, it's inherited by SequenceableCollection. >>>>> Looking through this code, I discovered that it builds a LinkedList of the >>>>> same size and then uses the at: and at:put: selector to copy the >>>>> transformed >>>>> values form the first list to the second. >>>>> >>>>> Knowing that at: and at:put: have O(n) complexity for linked lists, this >>>>> makes collect: an O(n^2) operation. On the other hand, this could easily >>>>> changed into O(n) by implementing collect: for LinkedList: >>>>> >>>>> collect: aBlock "Evaluate aBlock with each of the receiver's >>>>> elements as the argument. Collect the resulting values into a >>>>> collection like the receiver. Answer the new collection." >>>>> >>>>> | newCollection | >>>>> newCollection := self species new. >>>>> self do: >>>>> [:val | >>>>> newCollection add: (aBlock value: val)]. >>>>> ^ newCollection >>>>> >>>>> I profiled this using: >>>>> x := LinkedList new. >>>>> 1 to: 10000 do: [:n |x add: n]. >>>>> TimeProfileBrowser onBlock: [ x collect: [:i | i] ] >>>>> >>>>> and saw a improvement of: 795msec (old) vs. 6msec (new). >>>>> >>>>> I wonder therefore, if LinkedList is just seldomly used (in Java i.e. >>>>> nearly all lists use ArrayList nowadays)? Or would the system benefit from >>>>> this improvement? I could then look through the other methods >>>>> (collect:from:to: et. al.) and provide a patch. >>>>> >>>>> >>>>> best regards + thank's for creating such a beautiful system >>>>> Andreas Haufler >>>>> >>>> >>>> >>>> It does suffer from being a subclass of SequenceableCollection where >>>> default implementations assume O(1) at: and at:put: implementations… >>>> You're right it's not often used (at least not polymorphical to normal >>>> collections), and as such it's a tradeoff between keeping the >>>> implementation >>>> small (by using slow, but working super implementations), and >>>> reimplementing >>>> methods efficiently. >>>> >>>> In this case though, it seems Alain already noticed, and collect: has >>>> already been reimplemented efficiently in 1.4 >>>> >>>> Cheers, >>>> Henry >>>> >>>> >>> >>> Henrik, >>> Please note that I've only picked this as an example since it occurred >>> coincidently with my having just read the insightful slides of the >>> "[Pharo-project] Building a developer community" thread - but in light of >>> that... >>> >>> While your answer was good technically, it was not as good as it could be >>> for "building Pharo's developer community". Here a "visitor" with >>> reasonable Smalltalk ability extended a helping hand. The response returned >>> was a polite "we are doing good on our own thanks" - which is fine except >>> except it does not draw them in. An alternative might have included "its >>> already been done but come and have a look at it. It would be great if you >>> could help out with (other stuff)" >>> >>> Now some disclaimers... >>> * I did stretch the example since Alain is a third party whom you can't just >>> throw Andreas at unannounced. >>> * There has been little time for anyone else to answer >>> * I don't mean to posts should be constrained by kid gloves. >>> >>> Hopefully though this is a useful perspective to mix in with everything else >>> important. >>> warm regards, >>> Ben >>> >
