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
>
