- Pharo-dev - lists.pharo.org

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

by Ralph Boland

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

May 7, 2010

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

by Igor Stasenko

On 8 May 2010 02:07, Nicolas Cellier <nicolas.cellier.aka.nice(a)gmail.com> wrote: > 2010/5/8 Henrik Johansen <henrik.s.johansen(a)veloxit.no>: >> 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 >> <nicolas.cellier.aka.nice(a)gmail.com>: >> >>> 2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice(a)gmail.com>: >>>> >>>> 2010/5/7 Igor Stasenko <siguctua(a)gmail.com>: >>>>> >>>>> On 7 May 2010 23:47, Lukas Renggli <renggli(a)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(a)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(a)lists.gforge.inria.fr >>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>> >>>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

May 7, 2010

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

by Nicolas Cellier

2010/5/8 Henrik Johansen <henrik.s.johansen(a)veloxit.no>: > 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 > <nicolas.cellier.aka.nice(a)gmail.com>: > >> 2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice(a)gmail.com>: >>> >>> 2010/5/7 Igor Stasenko <siguctua(a)gmail.com>: >>>> >>>> On 7 May 2010 23:47, Lukas Renggli <renggli(a)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(a)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(a)lists.gforge.inria.fr >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

May 7, 2010

Re: [Pharo-project] Set + collect:

by Nicolas Cellier

2010/5/6 GermÃ¡n Leiva <leivagerman(a)gmail.com>: > 2010/5/3 StÃ©phane DucasseÂ <stephane.ducasse(a)inria.fr> >> >> > Hi, this is my first post (please be gentle xD) >> >> Thanks! >> > xD > >> >> > >> > The #collect: message commonly return a new collection like the >> > receiver, but this is really unpractical in some cases >> > >> > e.g. >> > col := Set with: 'one'->1 with: 'two'->2 with: 'dos'->2. >> > (col collect: [:each | each value ]) sum >> >> In VW you get the same. >> > Yes > >> > In this example #sum will return 3 instead of 5 (I searched a test for >> > #sum but I didnÂ´t find it). >> > >> > Ok, I can use the message #asBag (or something like that) but does the >> > second line have to depend on the type of the receiver (i.e. the type of >> > col)? >> >> I think that this is the invariant for collect: ? >> > I didnÂ´t understand that. > I'll like that this lineÂ (col collect: [:each | each value ]) sum > always returns 5 independently of the class ofÂ colÂ (ifÂ colÂ has the > elementsÂ 'one'->1Â ,Â 'two'->2Â andÂ 'dos'->2). > >> > For example, the implementation of #collect: in SortedCollection returns >> > an OrderedCollection (in the current image) >> >> in VW too >> > Yes, I like that.Â I just put the example to show thatÂ #collect:Â not always > returns a new collection like the receiver. > >> > and in other dialects the message #collect: when the receiver is a Set >> > returns a Bag ... >> >> which ones? >> > > In IBM VisualAge 6.0 returns a Bag (in InstantiationsÂ VAÂ 7.5.2 returns a > Set). > >> > Basically, what do you think of an implementation like this? >> > >> > Set >> collect: aBlock >> > Â "Evaluate aBlock with each of the receiver's elements as the argument. >> > Â Collect the resulting values into a Bag. Answer the new collection." >> > Â | newBag | >> > Â newBag := Bag new: self size. >> > Â array do: [:each | each ifNotNil: [newBag add: (aBlock value: each)]]. >> > Â ^ newBag > > 2010/5/4 Nicolas CellierÂ <nicolas.cellier.aka.nice(a)gmail.com> >> >> True.It can be impractical, but no need to change #collect: >> Please use #detectSum: >> >> (Set with: 'one'->1 with: 'two'->2 with: 'dos'->2) detectSum: [:e |e >> value]. >> >> >> or #collect:as: >> >> ((Set with: 'one'->1 with: 'two'->2 with: 'dos'->2) collect: [:e |e >> value] as: Array) sum. >> >> Nicolas > > Nice =) I didn't know those messages (although IMHO the name #detectSum: is > not pretty - I'm thinking aloud here ... #acummulateSum: or: directly #sum: > ...?) Sure, the name is just bad... I usually reimplement #sumOf: #maxOf: etc... or just #sum: #accumulateSum: sounds a bit like #cumulativeSum: (Matlab cumsum) (1 to: 5) cumulativeSum: [:e | e squared] -> #( 1 5 16 32 57 ) This message is not in Pharo nor Squeak though > The reason I'm proposing to change the Set >> #collect: implementation is > because the only situtation when you need that #collect: returns a Set is > when you didn't want duplications and for that is really nice to explicity > send the message asSet. > In all other cases a Bag is all you need as response to collect (when > collect is sended to a Set). Ah, if you come with a Rationale, that makes sense. I first thought you were willing to change core just to solve a specific problem > If you say this is counterproductive and the change will generate more > headaches than happiness I understand xD > Cheers, > I just can't say... The problem is we never know which code will break... This would deserve further inquiries. All I can say is #collect:as: fits perfectly your needs. It's always possible to change the core API. We recently changed Dictionary keys to answer an Array rather than a Set. It was rude because an Array cannot #add: nor #remove: The rationale was: - homegeneity with #values which did already answer an Array rather than a Bag, bonus: the #keys are now sorted like the #values - performance - because Arrays are much faster than Sets - core image analysis showing very few usage of add:/remove: on keys. - low upgrade cost (just adding an explicit asSet here and there like you're proposing). We also changed Dictionary>>collect: to answer a Dictionary rather than an OrderedCollection in Squeak 3.10 (or a Bag in very old st80). I also have the feeling that Bags are a bit segregated these days... Nicolas >> >> >> 2010/5/3 GermÃ¡n Leiva <leivagerman(a)gmail.com>: >> > Hi, this is my first post (please be gentle xD) >> > >> > The #collect: message commonly return a new collectionÂ like the >> > receiver, >> > but this is really unpractical in some cases >> > e.g. >> > col := Set with: 'one'->1 with: 'two'->2 with: 'dos'->2. >> > (col collect: [:each | each value ]) sum >> > In this example #sum will return 3 instead of 5 (I searched a test for >> > #sum >> > but I didnÂ´t find it). >> > >> > Ok, I can use the message #asBag (or something like that) but does the >> > second line have to depend on the type of theÂ receiver (i.e. the type of >> > col)? >> > For example, the implementation of #collect: in SortedCollection returns >> > an >> > OrderedCollection (in the current image) and in other dialects the >> > message >> > #collect: when the receiver is a Set returns a Bag ... >> > >> > Basically, what do you think of an implementation like this? >> > >> > Set >> collect: aBlock >> > Â "Evaluate aBlock with each of the receiver's elements as the argument. >> > Â Collect the resulting values into a Bag. AnswerÂ the new collection." >> > Â | newBag | >> > Â newBag := Bag new: self size. >> > Â array do: [:each | each ifNotNil: [newBag add: (aBlock value: each)]]. >> > Â ^ newBag >> > Cordially, >> > -- >> > GermÃ¡n Leiva >> > LeivaGerman(a)gmail.com >> > >> > _______________________________________________ >> > Pharo-project mailing list >> > Pharo-project(a)lists.gforge.inria.fr >> > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > -- > GermÃ¡n Leiva > LeivaGerman(a)gmail.com > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

May 7, 2010

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

by Henrik Johansen

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 <nicolas.cellier.aka.nice(a)gmail.com >: > 2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice(a)gmail.com>: >> 2010/5/7 Igor Stasenko <siguctua(a)gmail.com>: >>> On 7 May 2010 23:47, Lukas Renggli <renggli(a)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(a)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(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

May 7, 2010

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

by Nicolas Cellier

2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice(a)gmail.com>: > 2010/5/7 Igor Stasenko <siguctua(a)gmail.com>: >> On 7 May 2010 23:47, Lukas Renggli <renggli(a)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(a)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(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> >

May 7, 2010

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

by Nicolas Cellier

2010/5/7 Igor Stasenko <siguctua(a)gmail.com>: > On 7 May 2010 23:47, Lukas Renggli <renggli(a)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(a)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(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

May 7, 2010

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

by Igor Stasenko

On 7 May 2010 23:47, Lukas Renggli <renggli(a)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. > Lukas > > -- > Lukas Renggli > www.lukas-renggli.ch > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

May 7, 2010

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

by StÃ©phane Ducasse

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 >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

May 7, 2010

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

by Lukas Renggli

> 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

May 7, 2010