[Pharo-project] 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
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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 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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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
On 7 May 2010 23:47, Lukas Renggli <renggli@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
2010/5/7 Igor Stasenko <siguctua@gmail.com>:
On 7 May 2010 23:47, Lukas Renggli <renggli@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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2010/5/7 Igor Stasenko <siguctua@gmail.com>:
On 7 May 2010 23:47, Lukas Renggli <renggli@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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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@gmail.com
:
2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2010/5/7 Igor Stasenko <siguctua@gmail.com>:
On 7 May 2010 23:47, Lukas Renggli <renggli@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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2010/5/8 Henrik Johansen <henrik.s.johansen@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@gmail.com>:
2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2010/5/7 Igor Stasenko <siguctua@gmail.com>:
On 7 May 2010 23:47, Lukas Renggli <renggli@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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On 8 May 2010 02:07, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
2010/5/8 Henrik Johansen <henrik.s.johansen@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@gmail.com>:
2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2010/5/7 Igor Stasenko <siguctua@gmail.com>:
On 7 May 2010 23:47, Lukas Renggli <renggli@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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
Den 8. mai 2010 kl. 01.20 skrev Igor Stasenko <siguctua@gmail.com>:
On 8 May 2010 02:07, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com
wrote: 2010/5/8 Henrik Johansen <henrik.s.johansen@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. 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
Nicolas
Den 8. mai 2010 kl. 00.06 skrev Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2010/5/8 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2010/5/7 Igor Stasenko <siguctua@gmail.com>:
On 7 May 2010 23:47, Lukas Renggli <renggli@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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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
On Sat, 8 May 2010, Igor Stasenko wrote:
On 7 May 2010 23:47, Lukas Renggli <renggli@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.
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 Pharo-project@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
participants (6)
-
Henrik Johansen -
Igor Stasenko -
Levente Uzonyi -
Lukas Renggli -
Nicolas Cellier -
Stéphane Ducasse