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
