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
