[Pharo-project] another fun case for Linked>>add:
nicolas.cellier.aka.nice at gmail.com
Fri May 7 18:05:19 EDT 2010
2010/5/7 Igor Stasenko <siguctua at gmail.com>:
> On 7 May 2010 23:47, Lukas Renggli <renggli at gmail.com> wrote:
>>> He had the idea that it would be nice to be able to add any object to a LinkedList, instead of just Link subclasses. (IIRC, 'like you can in Ruby' ;))
>>> So we added ValueLink as the common pattern for "A link with an object in it", which is now the default if you add an object which itself is not a link.
>>> Makes it much more convenient to actually use a LinkedList, ref. f.ex. the Stack implementation.
>> LinkedList is used internally by the process scheduler to handle
>> processes, I don't think that it is ment to be used as a public
>> collection class. For probably all applications it is slower and uses
>> more memory than an OrderedCollection.
> OrderedCollection's addLast/removeFirst/removeLast, is enough to use
> them as lists.
> About performance, i am little concerned.
> Linked lists is good , that is costs you a constant time for each new
> element you adding.
> While for OrderedCollections it vary depending on container state. In
> most cases, it costs you as little as for linked lists, but when
> contained is not big enough to hold all elements - then it has to grow
> and consuming a lot more time comparing to adding a previous element.
Yes, LinkedList is most interesting when you add:after:/remove: in between...
OrderedCollection also isn't at best when used as FIFO because repeted
addLast/removeFirst will trigger a makeRoomAtLast.
It might be better to handle a cyclic index.
For example, I would maintain firstIndex and size in inst vars:
array size > size ifFalse: [self grow].
array atWrap: firstIndex + size put: anObject.
size := size + 1.
| firstObject |
firstObject := array at: firstIndex.
array at: firstIndex put: nil.
firstIndex := firstIndex \\ array size + 1.
size := size - 1.
| grown end |
grown := Array new: array size + self growSize.
end := (firstIndex + size - 1 min: array size) - firstIndex + 1.
grown replaceFrom: 1 to: end with: array starting at: firstIndex.
grown replaceFrom: end +1 to: size with: array startingAt; 1.
array := grown
Of course, you still pay the grow...
>> Lukas Renggli
>> Pharo-project mailing list
>> Pharo-project at lists.gforge.inria.fr
> Best regards,
> Igor Stasenko AKA sig.
> Pharo-project mailing list
> Pharo-project at lists.gforge.inria.fr
More information about the Pharo-dev