another fun case for Linked>>add:
Locked
another fun case for Linked>>add:
 
|
LinkedList>>add: aLinkOrObject
"Add aLink to the end of the receiver's list. Answer aLink." ^self addLast: aLinkOrObject LinkedList>>addLast: aLinkOrObject "Add aLink to the end of the receiver's list. Answer aLink." |aLink| aLink := aLinkOrObject asLink. self isEmpty ifTrue: [firstLink := aLink] ifFalse: [lastLink nextLink: aLink]. lastLink := aLink. ^aLink Object>>asLink "Answer a string that represents the receiver." ^ ValueLink value: self In squeak there is no such asLink.... We need a database with all the history to know which change introduced this change. Henrik do you remember why you introduce this change? Stef _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
Yes, this was somehting Nico Schwartz and I did during the sprint.
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. Sort of similar to what was done in Squeak to add nils to sets, actually. Cheers, Henry On May 6, 2010, at 9:25 52AM, Stéphane Ducasse wrote: > LinkedList>>add: aLinkOrObject > "Add aLink to the end of the receiver's list. Answer aLink." > > ^self addLast: aLinkOrObject > > LinkedList>>addLast: aLinkOrObject > "Add aLink to the end of the receiver's list. Answer aLink." > |aLink| > aLink := aLinkOrObject asLink. > self isEmpty > ifTrue: [firstLink := aLink] > ifFalse: [lastLink nextLink: aLink]. > lastLink := aLink. > ^aLink > > Object>>asLink > "Answer a string that represents the receiver." > > ^ ValueLink value: self > > > In squeak there is no such asLink.... > We need a database with all the history to know which change introduced this change. > Henrik do you remember why you introduce this change? > > Stef > > > > > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
On May 7, 2010, at 3:08 33PM, Henrik Johansen wrote: > Yes, this was somehting Nico Schwartz and I did during the sprint. > > 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. > > Sort of similar to what was done in Squeak to add nils to sets, actually. > > Cheers, > Henry Cheers, Henry > > > On May 6, 2010, at 9:25 52AM, Stéphane Ducasse wrote: > >> LinkedList>>add: aLinkOrObject >> "Add aLink to the end of the receiver's list. Answer aLink." >> >> ^self addLast: aLinkOrObject >> >> LinkedList>>addLast: aLinkOrObject >> "Add aLink to the end of the receiver's list. Answer aLink." >> |aLink| >> aLink := aLinkOrObject asLink. >> self isEmpty >> ifTrue: [firstLink := aLink] >> ifFalse: [lastLink nextLink: aLink]. >> lastLink := aLink. >> ^aLink >> >> Object>>asLink >> "Answer a string that represents the receiver." >> >> ^ ValueLink value: self >> >> >> In squeak there is no such asLink.... >> We need a database with all the history to know which change introduced this change. >> Henrik do you remember why you introduce this change? >> >> Stef >> >> >> >> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
In reply to this post by Henrik Sperre Johansen
> 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. Lukas -- Lukas Renggli www.lukas-renggli.ch _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
In reply to this post by Henrik Sperre Johansen
Thanks henrik for the explanation.
I'm not sure that I do not want to keep this class implementation minimal because it is only used by the scheduler. stef >> Yes, this was somehting Nico Schwartz and I did during the sprint. >> >> 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. >> >> Sort of similar to what was done in Squeak to add nils to sets, actually. >> >> Cheers, >> Henry > Which of course makes it all the more important that it actually returns aLink, rather than aLinkOrObject. > > Cheers, > Henry > >> >> >> On May 6, 2010, at 9:25 52AM, Stéphane Ducasse wrote: >> >>> LinkedList>>add: aLinkOrObject >>> "Add aLink to the end of the receiver's list. Answer aLink." >>> >>> ^self addLast: aLinkOrObject >>> >>> LinkedList>>addLast: aLinkOrObject >>> "Add aLink to the end of the receiver's list. Answer aLink." >>> |aLink| >>> aLink := aLinkOrObject asLink. >>> self isEmpty >>> ifTrue: [firstLink := aLink] >>> ifFalse: [lastLink nextLink: aLink]. >>> lastLink := aLink. >>> ^aLink >>> >>> Object>>asLink >>> "Answer a string that represents the receiver." >>> >>> ^ ValueLink value: self >>> >>> >>> In squeak there is no such asLink.... >>> We need a database with all the history to know which change introduced this change. >>> Henrik do you remember why you introduce this change? >>> >>> Stef >>> >>> >>> >>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
In reply to this post by Lukas Renggli
On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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. > Lukas > > -- > Lukas Renggli > www.lukas-renggli.ch > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
2010/5/7 Igor Stasenko <[hidden email]>:
> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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 >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
2010/5/8 Nicolas Cellier <[hidden email]>:
> 2010/5/7 Igor Stasenko <[hidden email]>: >> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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 firstIndex := 1 > > Of course, you still pay the grow... > > Nicolas > >>> Lukas >>> >>> -- >>> Lukas Renggli >>> www.lukas-renggli.ch >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> >> -- >> Best regards, >> Igor Stasenko AKA sig. >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
As Nicolas described, linkedlists certainly have their usecases.
I think you might be blurring cause and effect when using is only used in process handling, as an argument why the easier-to-use, no noticeable performance overhead (but slightly more complex implementation wise) version should be reverted. Cheers, Henry Den 8. mai 2010 kl. 00.06 skrev Nicolas Cellier <[hidden email] >: > 2010/5/8 Nicolas Cellier <[hidden email]>: >> 2010/5/7 Igor Stasenko <[hidden email]>: >>> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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 >>>> [hidden email] >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >>> >>> >>> -- >>> Best regards, >>> Igor Stasenko AKA sig. >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
2010/5/8 Henrik Johansen <[hidden email]>:
> As Nicolas described, linkedlists certainly have their usecases. > > I think you might be blurring cause and effect when using is only used in > process handling, as an argument why the easier-to-use, no noticeable > performance overhead (but slightly more complex implementation wise) version > should be reverted. > > Cheers, > Henry > Personnally, I like a LinkedList being able to hide the Link the way Dictionary hides the Association. http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-May/117262.html http://lists.squeakfoundation.org/pipermail/beginners/2008-July/004835.html Nicolas > Den 8. mai 2010 kl. 00.06 skrev Nicolas Cellier > <[hidden email]>: > >> 2010/5/8 Nicolas Cellier <[hidden email]>: >>> >>> 2010/5/7 Igor Stasenko <[hidden email]>: >>>> >>>> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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 >>>>> [hidden email] >>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>> >>>> >>>> >>>> >>>> -- >>>> Best regards, >>>> Igor Stasenko AKA sig. >>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> [hidden email] >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
On 8 May 2010 02:07, Nicolas Cellier <[hidden email]> wrote:
> 2010/5/8 Henrik Johansen <[hidden email]>: >> As Nicolas described, linkedlists certainly have their usecases. >> >> I think you might be blurring cause and effect when using is only used in >> process handling, as an argument why the easier-to-use, no noticeable >> performance overhead (but slightly more complex implementation wise) version >> should be reverted. >> >> Cheers, >> Henry >> > > Personnally, I like a LinkedList being able to hide the Link the way > Dictionary hides the Association. > > http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-May/117262.html > http://lists.squeakfoundation.org/pipermail/beginners/2008-July/004835.html > yeah, i think its protocol could have two entry points: - #add: for adding an object to list - #addLink: for linking a link to list so, that, #add: always creates a new instance of ValueLink , without asking object to do #asLink and then sends #addLink: , which does the rest. > Nicolas > >> Den 8. mai 2010 kl. 00.06 skrev Nicolas Cellier >> <[hidden email]>: >> >>> 2010/5/8 Nicolas Cellier <[hidden email]>: >>>> >>>> 2010/5/7 Igor Stasenko <[hidden email]>: >>>>> >>>>> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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 >>>>>> [hidden email] >>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Best regards, >>>>> Igor Stasenko AKA sig. >>>>> >>>>> _______________________________________________ >>>>> Pharo-project mailing list >>>>> [hidden email] >>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>> >>>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
In reply to this post by Stéphane Ducasse
> +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. > Given that the amortized cost is still O(1) per add or remove when using OrderedCollections I think the cost of the grows can be ignored unless the OrderedCollections are so large as to cause memory or memory management problems or if your algorithm is real time and cannot tolerate the occasional slowdown during a grow operation. In the latter situation I ask: why are you using an automatic garbage collected language such as Smalltalk? I expect the performance of OrderedCollections used as stacks or queues to be good compared to linked lists. Regards, Ralph Boland -- Quantum Theory cannot save us from the tyranny of a deterministic universe but it does give God something to do _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
In reply to this post by Igor Stasenko
Den 8. mai 2010 kl. 01.20 skrev Igor Stasenko <[hidden email]>: > On 8 May 2010 02:07, Nicolas Cellier <[hidden email] > > wrote: >> 2010/5/8 Henrik Johansen <[hidden email]>: >>> As Nicolas described, linkedlists certainly have their usecases. >>> >>> I think you might be blurring cause and effect when using is only >>> used in >>> process handling, as an argument why the easier-to-use, no >>> noticeable >>> performance overhead (but slightly more complex implementation >>> wise) version >>> should be reverted. >>> >>> Cheers, >>> Henry >>> >> >> Personnally, I like a LinkedList being able to hide the Link the way >> Dictionary hides the Association. >> >> http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-May/117262.html >> http://lists.squeakfoundation.org/pipermail/beginners/2008-July/004835.html >> > > yeah, i think its protocol could have two entry points: > - #add: for adding an object to list > - #addLink: for linking a link to list > > so, that, #add: always creates a new instance of ValueLink , without > asking object to do #asLink > and then sends #addLink: , which does the rest. complicated protocol, and is backwards-incompatible. Cheers, Henry PS. We DID consider other possible solutions before deciding to add "yet another" as... method to Object > >> Nicolas >> >>> Den 8. mai 2010 kl. 00.06 skrev Nicolas Cellier >>> <[hidden email]>: >>> >>>> 2010/5/8 Nicolas Cellier <[hidden email]>: >>>>> >>>>> 2010/5/7 Igor Stasenko <[hidden email]>: >>>>>> >>>>>> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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 >>>>>>> [hidden email] >>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Best regards, >>>>>> Igor Stasenko AKA sig. >>>>>> >>>>>> _______________________________________________ >>>>>> Pharo-project mailing list >>>>>> [hidden email] >>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >> _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
Thanks for the info :)
>> yeah, i think its protocol could have two entry points: >> - #add: for adding an object to list >> - #addLink: for linking a link to list >> >> so, that, #add: always creates a new instance of ValueLink , without >> asking object to do #asLink >> and then sends #addLink: , which does the rest. > I don't quite see the appeal in an approach which both has a more complicated protocol, and is backwards-incompatible. > > Cheers, > Henry > > PS. We DID consider other possible solutions before deciding to add "yet another" as... method to Object > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: another fun case for Linked>>add:
|
|
In reply to this post by Igor Stasenko
On Sat, 8 May 2010, Igor Stasenko wrote:
> On 7 May 2010 23:47, Lukas Renggli <[hidden email]> 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. No. These methods make it good enough (or at least they should, but we know that they don't) to use OrderedCollections as stacks, queues or double-ended queues (which are the common cases), but adding an element before or after another takes O(n) time, compared to lists' O(1). Though this feature can only be used if we allow the users to reference the links directly, otherwise lists have no advantage. > > 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. That would be true if there was no GC. And as Ralph pointed out, the amortized cost of adding/removing elements to/from the ends of an OrderedCollection is O(1) (or at least it should be, but it's not). Levente > >> Lukas >> >> -- >> Lukas Renggli >> www.lukas-renggli.ch >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
«
Return to Pharo Smalltalk Developers
|
1 view|%1 views
| Free forum by Nabble | Edit this page |