Iterating and removing items from OrderedCollections
Locked
Iterating and removing items from OrderedCollections
 
|
Hello all
I've got an OrderedCollection that is normally a fixed size (let's say 10 elements). Each element in the collection is another an object or nil. So for example, at a point in time it might look like [nil, nil, Object, nil, Object, Object, nil, nil, Object, nil] What I want is to be able to resize the collection. Making it bigger is no problem for me, I can just add nils to the end of the collection. Making it smaller is involving a little bit of pain. I can see ways of doing it but theyr'e not elegant and I'm sure there are cleaner ways of doing it. If I made the above queue smaller I'd basically remove the nils starting from the beginning. So a resize to size 7 would give me [ Object, Object, Object, nil, nil, Object, nil] i.e. the first three nils have been removed. Does anybody have any comments on appropriate code to handle this? If not, I'll go with the ugly stuff but it would be nice to know the correct SmallTalk way. Many thanks for any suggestions. Ian _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
Why are there nils in the middle of the queue?
The obvious thing is to use a linked structure or one which has amortised constant time addition of elements, and simply count how many items have been added to the queue to limit its size.
On 9/18/08, Ian J Cottee <[hidden email]> wrote:
Hello all _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Ian J Cottee-3
Am 18.09.2008 um 10:06 schrieb Ian J Cottee: > Hello all > > I've got an OrderedCollection that is normally a fixed size (let's say > 10 elements). Each element in the collection is another an object or > nil. So for example, at a point in time it might look like > > [nil, nil, Object, nil, Object, Object, nil, nil, Object, nil] > > What I want is to be able to resize the collection. Making it bigger > is no problem for me, I can just add nils to the end of the > collection. Making it smaller is involving a little bit of pain. I can > see ways of doing it but theyr'e not elegant and I'm sure there are > cleaner ways of doing it. If I made the above queue smaller I'd > basically remove the nils starting from the beginning. So a resize to > size 7 would give me > > [ Object, Object, Object, nil, nil, Object, nil] > > i.e. the first three nils have been removed. > > Does anybody have any comments on appropriate code to handle this? If > not, I'll go with the ugly stuff but it would be nice to know the > correct SmallTalk way. > > Many thanks for any suggestions. I guess it doesn't get much more elegant and efficient than start := coll findFirst: [:each | each ~~ nil]. coll removeFirst: start-1. ... unless you add a specific method to OC. - Bert - _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Marcin Tustin
Hi
It's emulating a conveyor belt. The 10 elements are slots on the belt that a machine at one end can place items into. Every x seconds the belt moves on one step. If the first machine hasn't put an item in the slot, the slot is empty. At the other end, if the there's an item in the slot when it gets to the front of the queue - that's given to the next machine. So depending on what the loading machine is doing, you can end up with gaps on the belt. However, as it's a simulation the user may wish to change the size of the belt - in which case I have to remove slots with nothing in them (I can't remove slots which do have items on them for obvious reasons). On Thu, Sep 18, 2008 at 9:31 AM, Marcin Tustin <[hidden email]> wrote: > Why are there nils in the middle of the queue? > > The obvious thing is to use a linked structure or one which has amortised > constant time addition of elements, and simply count how many items have > been added to the queue to limit its size. > > > On 9/18/08, Ian J Cottee <[hidden email]> wrote: >> >> Hello all >> >> I've got an OrderedCollection that is normally a fixed size (let's say >> 10 elements). Each element in the collection is another an object or >> nil. So for example, at a point in time it might look like >> >> [nil, nil, Object, nil, Object, Object, nil, nil, Object, nil] >> >> What I want is to be able to resize the collection. Making it bigger >> is no problem for me, I can just add nils to the end of the >> collection. Making it smaller is involving a little bit of pain. I can >> see ways of doing it but theyr'e not elegant and I'm sure there are >> cleaner ways of doing it. If I made the above queue smaller I'd >> basically remove the nils starting from the beginning. So a resize to >> size 7 would give me >> >> [ Object, Object, Object, nil, nil, Object, nil] >> >> i.e. the first three nils have been removed. >> >> Does anybody have any comments on appropriate code to handle this? If >> not, I'll go with the ugly stuff but it would be nice to know the >> correct SmallTalk way. >> >> Many thanks for any suggestions. >> >> Ian >> _______________________________________________ >> Beginners mailing list >> [hidden email] >> http://lists.squeakfoundation.org/mailman/listinfo/beginners > > > _______________________________________________ > Beginners mailing list > [hidden email] > http://lists.squeakfoundation.org/mailman/listinfo/beginners > > Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Bert Freudenberg
On Thu, Sep 18, 2008 at 9:44 AM, Bert Freudenberg <[hidden email]> wrote:
> I guess it doesn't get much more elegant and efficient than > > start := coll findFirst: [:each | each ~~ nil]. > coll removeFirst: start-1. > Interesting - many thanks Bert. I'll give that a try later on. _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Ian J Cottee-3
Would this be O(n^2) to remove all nils?
In any case, if this is a conveyor belt, then you should almost certainly be using a linke data structure, and iterate over the structure to delete the unwanted links.
On 9/18/08, Bert Freudenberg <[hidden email]> wrote:
_______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
At Thu, 18 Sep 2008 10:00:15 +0100,
Marcin Tustin wrote: > > Would this be O(n^2) to remove all nils? Not in a way it matters. OrderedCollection moves items not eagarly. > In any case, if this is a conveyor belt, then you should almost certainly be using a linke data structure, and iterate > over the structure to delete the unwanted links. No in two reasons; 1) he wasn't talking about removing items in the middle and 2) OrderedCollection is usually more efficient than the naive LinkedList, as less dereferencing. (And, it could get more benefits from using array manipulation primitives like replaceFrom:to:, but it can't at least for addFirst:.) -- Yoshiki _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Marcin Tustin
Am 18.09.2008 um 11:00 schrieb Marcin Tustin: > Would this be O(n^2) to remove all nils? This only removes nils from the start. If n is the size of the collection and m the number of nils at its beginning then it's only O(m). > start := coll findFirst: [:each | each ~~ nil]. > coll removeFirst: start-1. - Bert - _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Marcin Tustin
On 9/18/08, Yoshiki Ohshima <[hidden email]> wrote:
At Thu, 18 Sep 2008 10:00:15 +0100, Do you mean that it will do a lazy delete?
> In any case, if this is a conveyor belt, then you should almost certainly be using a linke data structure, and iterate Look at the original example. and 2) OrderedCollection is usually more efficient than the I think this would be an empirical question.
-- Yoshiki _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Ian J Cottee-3
Ah, that's a much better description. So you actually don't want to
remove nils from the start, but simply remove enough until the size is small enough? Now that's simple: belt size - desiredSize timesRepeat: [belt remove: nil ifAbsent: []]. And to answer Marcin's next question, yes, that would be O(m^2). It doesn't matter for Ian's purpose I think, but an O(n) version would be toRemove := belt size - desiredSize. belt removeAllSuchThat: [:each | each == nil and: [(toRemove := toRemove-1) >= 0]]. ... which is obviously less elegant ;) - Bert - Am 18.09.2008 um 10:49 schrieb Ian J Cottee: > Hi > > It's emulating a conveyor belt. The 10 elements are slots on the belt > that a machine at one end can place items into. Every x seconds the > belt moves on one step. If the first machine hasn't put an item in the > slot, the slot is empty. At the other end, if the there's an item in > the slot when it gets to the front of the queue - that's given to the > next machine. So depending on what the loading machine is doing, you > can end up with gaps on the belt. > > However, as it's a simulation the user may wish to change the size of > the belt - in which case I have to remove slots with nothing in them > (I can't remove slots which do have items on them for obvious > reasons). >> >> On 9/18/08, Ian J Cottee <[hidden email]> wrote: >>> >>> Hello all >>> >>> I've got an OrderedCollection that is normally a fixed size (let's >>> say >>> 10 elements). Each element in the collection is another an object or >>> nil. So for example, at a point in time it might look like >>> >>> [nil, nil, Object, nil, Object, Object, nil, nil, Object, nil] >>> >>> What I want is to be able to resize the collection. Making it bigger >>> is no problem for me, I can just add nils to the end of the >>> collection. Making it smaller is involving a little bit of pain. I >>> can >>> see ways of doing it but theyr'e not elegant and I'm sure there are >>> cleaner ways of doing it. If I made the above queue smaller I'd >>> basically remove the nils starting from the beginning. So a resize >>> to >>> size 7 would give me >>> >>> [ Object, Object, Object, nil, nil, Object, nil] >>> >>> i.e. the first three nils have been removed. >>> >>> Does anybody have any comments on appropriate code to handle this? >>> If >>> not, I'll go with the ugly stuff but it would be nice to know the >>> correct SmallTalk way. >>> >>> Many thanks for any suggestions. >>> >>> Ian >>> _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Marcin Tustin
Am 18.09.2008 um 11:38 schrieb Marcin Tustin: > > > On 9/18/08, Yoshiki Ohshima <[hidden email]> wrote: At Thu, 18 Sep > 2008 10:00:15 +0100, > Marcin Tustin wrote: > > > > Would this be O(n^2) to remove all nils? > > Not in a way it matters. OrderedCollection moves items not eagarly. > > Do you mean that it will do a lazy delete? #removeFirst just nils out the first slot and moves the start index. Compaction only happens when adding elements and there is space at the beginning. - Bert - _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Bert Freudenberg
Am 18.09.2008 um 11:40 schrieb Bert Freudenberg: > belt size - desiredSize timesRepeat: [belt remove: nil ifAbsent: []]. > > And to answer Marcin's next question, yes, that would be O(m^2). Err, O(m*n). Need coffee. - Bert - _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Marcin Tustin
At Thu, 18 Sep 2008 10:38:52 +0100,
Marcin Tustin wrote: > > No in two reasons; 1) he wasn't talking about removing items in the > middle > > Look at the original example. Right. But still I think suggesting to use LinkedList here is not a good idea. > and 2) OrderedCollection is usually more efficient than the > naive LinkedList, as less dereferencing. (And, it could get more > benefits from using array manipulation primitives like > replaceFrom:to:, but it can't at least for addFirst:.) > > I think this would be an empirical question. Exacly. Measure the performance before suggesting a complex solution. -- Yoshiki _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Re: Iterating and removing items from OrderedCollections
|
|
In reply to this post by Bert Freudenberg
A reply to everyone who replied. Many thanks indeed. I really appreciate it.
The first example below is perfect for me so far in the small number of unit tests I've written. I'll do some more tomorrow. Now I just have to understand what it's doing ;) Ian PS My solution was about ten lines of code and very obviously procedural! On Thu, Sep 18, 2008 at 10:40 AM, Bert Freudenberg <[hidden email]> wrote: > Ah, that's a much better description. So you actually don't want to remove > nils from the start, but simply remove enough until the size is small > enough? Now that's simple: > > belt size - desiredSize timesRepeat: [belt remove: nil ifAbsent: []]. > > And to answer Marcin's next question, yes, that would be O(m^2). It doesn't > matter for Ian's purpose I think, but an O(n) version would be > > toRemove := belt size - desiredSize. > belt removeAllSuchThat: [:each | each == nil and: [(toRemove := toRemove-1) >>= 0]]. > > ... which is obviously less elegant ;) > > - Bert - > > Am 18.09.2008 um 10:49 schrieb Ian J Cottee: > >> Hi >> >> It's emulating a conveyor belt. The 10 elements are slots on the belt >> that a machine at one end can place items into. Every x seconds the >> belt moves on one step. If the first machine hasn't put an item in the >> slot, the slot is empty. At the other end, if the there's an item in >> the slot when it gets to the front of the queue - that's given to the >> next machine. So depending on what the loading machine is doing, you >> can end up with gaps on the belt. >> >> However, as it's a simulation the user may wish to change the size of >> the belt - in which case I have to remove slots with nothing in them >> (I can't remove slots which do have items on them for obvious >> reasons). >>> >>> On 9/18/08, Ian J Cottee <[hidden email]> wrote: >>>> >>>> Hello all >>>> >>>> I've got an OrderedCollection that is normally a fixed size (let's say >>>> 10 elements). Each element in the collection is another an object or >>>> nil. So for example, at a point in time it might look like >>>> >>>> [nil, nil, Object, nil, Object, Object, nil, nil, Object, nil] >>>> >>>> What I want is to be able to resize the collection. Making it bigger >>>> is no problem for me, I can just add nils to the end of the >>>> collection. Making it smaller is involving a little bit of pain. I can >>>> see ways of doing it but theyr'e not elegant and I'm sure there are >>>> cleaner ways of doing it. If I made the above queue smaller I'd >>>> basically remove the nils starting from the beginning. So a resize to >>>> size 7 would give me >>>> >>>> [ Object, Object, Object, nil, nil, Object, nil] >>>> >>>> i.e. the first three nils have been removed. >>>> >>>> Does anybody have any comments on appropriate code to handle this? If >>>> not, I'll go with the ugly stuff but it would be nice to know the >>>> correct SmallTalk way. >>>> >>>> Many thanks for any suggestions. >>>> >>>> Ian >>>> > > > _______________________________________________ > Beginners mailing list > [hidden email] > http://lists.squeakfoundation.org/mailman/listinfo/beginners > Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
«
Return to Squeak - Beginners
|
1 view|%1 views
| Free forum by Nabble | Edit this page |