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 >>
