2010/5/7 Igor Stasenko <[email protected]>:
> On 7 May 2010 23:47, Lukas Renggli <[email protected]> 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
>> [email protected]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
> _______________________________________________
> Pharo-project mailing list
> [email protected]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
