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

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Fri May 7 18:06:37 EDT 2010


2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
> 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
Oops, forgot
    firstIndex := 1

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