[Pharo-project] another fun case for Linked>>add:

Nicolas Cellier 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.
>>
> +1.
> 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:

addLast:anObject
    array size > size ifFalse: [self grow].
    array atWrap: firstIndex + size put: anObject.
    size := size + 1.
    ^anObject

removeFirst
    | firstObject |
    self emptyCheck.
    firstObject := array at: firstIndex.
    array at: firstIndex put: nil.
    firstIndex := firstIndex \\ array size + 1.
    size := size - 1.
    ^firstObject

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

Nicolas

>> Lukas
>>
>> --
>> Lukas Renggli
>> www.lukas-renggli.ch
>>
>> _______________________________________________
>> Pharo-project mailing list
>> Pharo-project at lists.gforge.inria.fr
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
> _______________________________________________
> Pharo-project mailing list
> Pharo-project at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>




More information about the Pharo-dev mailing list