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