Idiomatic deletion from a slice?

[Paul Lalonde]

I have a slice that I want to remove an object from in an arbitrary
position. The remove is made hideous by the possibility of removing
the last element:
// Remove the ith element
if i < len(s)-1 {
s = append(s[:i], s[i+1:]...)
} else {
s = s[:i]
}

This seems a tad inelegant. What's the idiom I'm missing?

Thanks,
Paul

[DisposaBoy]

... will let others comment on the idiomatic thing to do but if your slice doesn't need to be in-order then you can simply swap the element with the element at the end of the slice then reduce the slice by  one.

e.g. http://play.golang.org/p/BLKHqjgXWN

[Paul Lalonde]

Yes, that works for my current case, though maintaining order would
also be nice.
Clearly, I could also loop moving elements around. It just doesn't
feel idiomatic.
Paul

[Steven Blenkinsop]

This works:

s = append(s[:i], s[i+1:]...)

Recall that s[len(s):] is a zero length slice.

[Havy]

great

On 12月3日, 上午3时29分, Steven Blenkinsop <steven...@gmail.com> wrote:

[Brad Fitzpatrick]

Use a doubly-linked list if you want to maintain order and want to avoid copying stuff whenever you delete something:

http://golang.org/pkg/container/list/

Depends what you need and how big your data is.

[peterGo]

Paul,

Delete

a = append(a[:i], a[i+1:]...)

Slice Tricks
http://code.google.com/p/go-wiki/wiki/SliceTricks

Peter

[Rasmus Schultz]

This doesn't work for me, I'm going bonkers here...

for i, item := range list {

if item.id == listener.id {

// TODO this doesn't remove the item, instead it seems to add one!?!

list = append(list[:i], list[i+1:]...)

break

}

}

For some reason my list here comes out with removed item now duplicated instead of removed!

Should it be this hard to remove an item from a slice? how come we don't simply have more keywords/functions like append() for other common slice operations?

I read the SliceTricks page and I am none the wiser...

[Dan Kortschak]

Works here http://play.golang.org/p/WNd9wmkq9c

[Ross Salas]

Works here too.  I deleted item 5.  You may want to check value of listener.id.

http://play.golang.org/p/2NqcLNLBqu

On Sun, Mar 16, 2014 at 8:56 PM, Dan Kortschak <dan.ko...@adelaide.edu.au> wrote:

Works here http://play.golang.org/p/WNd9wmkq9c

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Rasmus Schultz]

Is it working differently if I'm deleting the last item in a slice?

I posted the whole thing here:

https://github.com/mindplay-dk/riot.go

[Dan Kortschak]

No, try it.

[andrew.b...@gree.co.jp]

Whenever i'm dealing with a small slice of pointers, i usually end up with something like this:

copy(s[i:], s[i+1:]) // shift

s[len(s)-1] = nil    // remove reference

s = s[:len(s)-1]     // reslice

e.g. http://play.golang.org/p/J9V0L0d55W

[Carlos Castillo]

The slice (list) that's being pulled out of the map on line #71 is not being assigned back into the map, so it still has the original slice bounds (when removing should have shortened it), as a result the last element is duplicated.

You should assign the list back to the map before breaking.

[Carlos Castillo]

Example: http://play.golang.org/p/DiwQ7XF3oP

[Matthew Zimmerman]

https://code.google.com/p/go-wiki/wiki/SliceTricks

[Rasmus Schultz]

Yes, I looked at that, it explains how to delete from a slice - isn't that what I'm doing in my code?

So I just set up a brand new Go 1.2.1 on my new computer tonight, and checked out my code and ran it - and now, what should be two calls, and was 3 calls on my other system, generates 5 calls on this system!

Could somebody run the test on their setup and compare the output?

=== RUN TestObservable

--- FAIL: TestObservable (0.00 seconds)

observable_test.go:23: LoadEvent handler #1: LoadEvent#1

observable_test.go:30: LoadEvent handler #2: LoadEvent#1

observable_test.go:37: SaveEvent once-handler #1: SaveEvent#1

observable_test.go:44: SaveEvent handler: SaveEvent#1

observable_test.go:44: SaveEvent handler: SaveEvent#2

observable_test.go:55: SaveEvent once-handler #2: SaveEvent#3

observable_test.go:44: SaveEvent handler: SaveEvent#3

observable_test.go:30: LoadEvent handler #2: LoadEvent#2

observable_test.go:30: LoadEvent handler #2: LoadEvent#2

observable_test.go:30: LoadEvent handler #2: LoadEvent#3

observable_test.go:30: LoadEvent handler #2: LoadEvent#3

observable_test.go:76: expected 2 calls to LoadEvent handler #2, got 5

FAIL

exit status 1

FAIL github.com/mindplay-dk/riot 0.512s

Meanwhile, I am none the wiser, and slice deletion, as explained on the wiki (and here) doesn't make a lick of sense to me.

It's making me feel pretty dumb. This must be the first and least idiomatic thing I've seen in Go so far - an operation this basic should not make you feel dumb, and should not require code that is, more or less, void of any semantics.

I love the simplicity of Go, but this doesn't seem simple at all - it seems unnecessarily complicated, and I'm more than a a little taken aback by this... :-/

Any better alternatives - or any hope of this improving in the future?

Thanks,

  Rasmus

[Sanjay]

It looks to me like you're retrieving a slice from a map by-value, modifying that slice, and not writing it back. I imagine it'll work if you do an assignment back to the map.

Sanjay

[Caleb Spare]

Sanjay beat me to describing your issue (you're modifying a copy of
the map slice without saving it back to the map).

It's really a straightforward application of 'append' and certainly
isn't "void of any semantics".

s1 := []string{"a", "b", "c", "d"}
i := 2
s2 := append(s1[:i], s1[i+1:]...) // ["a", "b", "d"]

This works for any (valid) slice index i. All it's saying is that s2
is composed of everything before index i (s1[:i]) and everything after
index i (s1[i+1:]). The ... is necessary because append takes a list
of elements for the second part (it's variadic). Note that this works
fine even if i == 0 or if i == len(s1)-1, in which case s1[:i] or
s1[i+1:] is empty, respectively.

If you were doing a lot of vector operations like this in your code,
you might consider using a custom slice type with methods to make it
look nicer. It doesn't look like there's a lot of that kind of stuff
going on in your linked code, though.

http://play.golang.org/p/IpvC4Vkf8V

[Rasmus Schultz]

I don't want to debate this at length, but this really isn't semantic:

s2 := append(s1[:i], s1[i+1:]...)

Semantic would be a keyword or something else that actually expresses deletion, e.g.:

delete s1[i];

I understand that's not how slices "work" in Go - because the slice itself is a value, and not an "object"... but from this example, it seems that's both good and bad - though most of the time thus far I have thought this was a good thing, when you want to manipulate an existing value, even for a simple manipulation like removing an item (or excluding it) this really doesn't come out legible at all... "parsing" all those parens and brackets and colons is hard...

Any chance Go will ever have something like e.g. macros or "inline" functions, which could be used to give name (thus adding semantics) to simple operations like these?

But back to the situation at hand -

> you might consider using a custom slice type with methods to make it look nicer

I really would like that - could you give an example of doing that?

Thanks guys.

[Caleb Spare]

On Tue, Mar 18, 2014 at 9:04 PM, Rasmus Schultz <ras...@mindplay.dk> wrote:
> I don't want to debate this at length, but this really isn't semantic:
>
> s2 := append(s1[:i], s1[i+1:]...)
>
> Semantic would be a keyword or something else that actually expresses
> deletion, e.g.:
>
> delete s1[i];

I'm not exactly sure what you're trying to say here. You seem to be
using a meaning of the word 'semantic' with which I'm not familiar.
Perhaps you mean 'obvious' or 'clear'.

To further your example, it would be even nicer if Go had a
doWhatIMean() function. That would make everything much simpler!

Lacking dedicated keywords and functions, we must write code that
expresses our intent.

Anecdotally, I have written a lot of Go code but only rarely (a half
dozen times at most) needed to remove something from the middle of a
slice. In these cases, the very most that was required to keep the
code clear was a quick comment (// Remove item at position i).

>
> I understand that's not how slices "work" in Go - because the slice itself
> is a value, and not an "object"... but from this example, it seems that's
> both good and bad - though most of the time thus far I have thought this was
> a good thing, when you want to manipulate an existing value, even for a
> simple manipulation like removing an item (or excluding it) this really
> doesn't come out legible at all... "parsing" all those parens and brackets
> and colons is hard...
>
> Any chance Go will ever have something like e.g. macros or "inline"
> functions, which could be used to give name (thus adding semantics) to
> simple operations like these?
>
> But back to the situation at hand -
>
>> you might consider using a custom slice type with methods to make it look
>> nicer
>
> I really would like that - could you give an example of doing that?

Really brief example:

http://play.golang.org/p/ynaArl0bRf

But again, from what I've seen of your code, I don't believe this is warranted.

[Jesse McNelis]

On Wed, Mar 19, 2014 at 3:04 PM, Rasmus Schultz <ras...@mindplay.dk> wrote:

I don't want to debate this at length, but this really isn't semantic:

s2 := append(s1[:i], s1[i+1:]...)

Semantic would be a keyword or something else that actually expresses deletion, e.g.:

delete s1[i];

But what would this mean? 

What should be the result of the operation?

The append example in slice tricks is very clear about the the result is.

You get a new slice that shares the same backing array as the previous slice, is one item shorter and with all the items moved up one slot.

A delete function could do that, but it would still have to return the new slice.

You could have, eg.

s2 := delete(s1,i)

But this hides all the side effects of the delete operation. Such as, that all pointers in to this slice's array are now broken.

The append() makes this obvious by clearly showing the copying that occurs to do the delete.

[Dan Kortschak]

The solution sent a couple of days ago is eminently readable when the
reader is accustomed to Go idiom:

func (listeners ListenerMap) remove(listener Listener) {
if list, present := listeners[listener.event_type]; present {

for i, item := range list {
if item.id == listener.id {

listeners[listener.event_type] = append(list[:i], list[i+1:]...)
break
}
}
}
}

Becoming accustomed takes time, but it comes.

On Tue, 2014-03-18 at 23:04 -0500, Rasmus Schultz wrote:
> I don't want to debate this at length, but this really isn't semantic:
>
> s2 := append(s1[:i], s1[i+1:]...)
>
> Semantic would be a keyword or something else that actually expresses
> deletion, e.g.:
>
> delete s1[i];
>
> I understand that's not how slices "work" in Go - because the slice itself
> is a value, and not an "object"... but from this example, it seems that's
> both good and bad - though most of the time thus far I have thought this
> was a good thing, when you want to manipulate an existing value, even for a
> simple manipulation like removing an item (or excluding it) this really
> doesn't come out legible at all... "parsing" all those parens and brackets

> and colons is *hard*...

[bga...@golang.org]

On Wednesday, March 19, 2014 12:04:50 AM UTC-4, Rasmus Schultz wrote:

delete s1[i];

Another thing to consider is that deleting an item from the middle of a slice is an expensive operation, resulting in potentially a lot of copying.  Because of this, one can argue that this *shouldn't* be an easy thing to do, to discourage its use when it's not appropriate. 

[Sebastien Binet]

agreed.
although (playing devil's advocate) one could imagine allowing the
delete builtin function to also take slices in addition to just maps
so:

m := map[int]string{0:"0", 1:"1", 2:"2"}
s := []string{"0","1","2"}
delete(m, 1)
delete(s, 1)

would be valid.

-s

[Rasmus Schultz]

> The solution sent a couple of days ago is eminently readable when the
> reader is accustomed to Go idiom

I have to disagree entirely - it may be I'm using the word "semantics" inappropriately here, but what I mean to say, is that append(list[:i], list[i+1:]...) does not communicate intent. If anything, the word "append" is misleading, since the resulting operation is the opposite of appending: deleting.

My point is, when I'm reading through a function that happens to delete something from a slice, I don't want to get distracted by misleading words and lengthy expressions for something is trivial as removing an item from a list.

Idioms or not, I don't understand how you can think that's a good thing. Code should be legible. It should be express intent. It should not force you to parse expressions or evaluate code for trivial operations.

Therefore, idioms or not, Caleb's example is useful, and I will be doing exactly that - though it still feels rather strange to me, having to write and maintain code for something as basic and common as this.

> Another thing to consider is that deleting an item from the middle of a slice is an expensive operation, resulting in potentially a lot of copying.  Because of this, one can argue that this *shouldn't* be an easy thing to do, to discourage its use when it's not appropriate

If you know that deletion from a slice is an expensive operation, that should be discouragement enough - you really think it's reasonable to punish people in situations where they do need to remove something from a list?

I actually was discouraged when I saw the "idiomatic" way to delete from a slice, and in this particular case, it directly influence the way this code is organized, and in this case, made it more complicated than necessary, and created some minor drawbacks.

My initial design had a boolean "once" flag on the Listener type, which would indicate whether it gets dispatched once or many times. When I realized how cumbersome it would be to remove items from the list, I instead went for a design where Sink as two ListenerMaps - a dedicated one for "once" listeners, and another one for "many" listeners.

Unfortunately, that design has a side effect: the order in which listeners get notified is now inherently different from the order in which you register listeners, because I have to now fire either the "once" or "many" listeners first.

The other problem is that, even if this trade-off in functionality is acceptable (and I don't know yet if it is) I still have to deal with the problem of removal, since listeners can get un-registered, too. This operation is now more complicated, since there are now two places to search for a listener. And sure, I could denormalize the model some more, by adding back the "once" flag to Listener, so I would know which map to look in, but, am I still making things simpler, or am I making them more complicated now?

I may be thinking or going about this all wrong, but it seems to me, in this case, "less is more" isn't working for me, it's working against me - it complicated the design, it made me accept a trade-off in functionality, and it made me lose a lot of time on issues that are (or ought to be) totally trivial.

Up until this point, I have come around and learned to like things that seemed odd to me at first, but this one is... I don't know... how come delete was deemed necessary for maps, but not for slices?

If you can think of a design approach that completely eliminates the need to delete from slices, I'm all ears.

If not, well, I guess if I'm the only one who doesn't love reading these lengthy expressions for trivial operations, well, I will go with Caleb's approach, and I guess I'll be doing a lot of copying and pasting ;-)

[Péter Szilágyi]

How can writing 

  slice = append(slice[:i], slice[i+1:]...)

instead of 

  delete(slice, element) 

lead to a different design???

Btw, delete is necessary for maps because maps are types deeply rooted within the Go runtime, requiring special runtime logic and constructs to work.

[Jan Mercl]

On Wed, Mar 19, 2014 at 2:55 PM, Rasmus Schultz <ras...@mindplay.dk> wrote:
>> The solution sent a couple of days ago is eminently readable when the
>> reader is accustomed to Go idiom
>

> I have to disagree entirely - it may be I'm using the word "semantics"
> inappropriately here, but what I mean to say, is that append(list[:i],
> list[i+1:]...) does not communicate intent. If anything, the word "append"
> is misleading, since the resulting operation is the opposite of appending:
> deleting.

The append communicates what's happening correctly. The deletion is in
this case a special case of append where two parts of a slice are
appended in such a way that wrt the original slice the result has 1
(or more in the general case), elements removed.

It's a bit like perfoming substraction by addition of a negated value.
Or implementing certain multiplications/divisions doing shifts etc.

It's probably useful to differentiate and think about it as two
things: the operation and its result. Which is what it really is.
Fuzzy packed operation and its result in one "thing" is the source of
the confusion here. (Or it could be surprising, like when adding
something to a number produces smaller result.)

I cannot talk for the Go team, but I believe this is WAI and no
delete(slice, index) feature will be added to the language.

-j

[Jesse McNelis]

On Thu, Mar 20, 2014 at 12:55 AM, Rasmus Schultz <ras...@mindplay.dk> wrote:

My point is, when I'm reading through a function that happens to delete something from a slice, I don't want to get distracted by misleading words and lengthy expressions for something is trivial as removing an item from a list.

A slice is not a list. The container/list package has a list if you need it.

Lists are great if you need to remove items from the middle.

The append() trick is not misleading, delete() would be misleading.

The operation you're doing isn't deleting, it's copying every value in a slice up one slot, overriding a certain slot and shortening the slice.

This is exactly the semantics that append() has and is a rather complicated set of operations to infer from the word 'delete'

[DV]

In general, I'm not too happy with how deleting from a slice needs to happen, but there are a few reasons for it:

1. A slice's backing store is just an array. Deleting from an array is actually not trivial in *any* language that has the C definition of arrays - it involves memory allocation (sometimes), copying (most of the time)

2. Even if there was a delete convenience operation on slices (ala map's delete), it would be just a wrapper on append anyway - I can't think of any other way to do it for storage that is essentially a C-style array. 

A slice is a nice abstraction on top of an array - nothing else. It's *not* a linked list (in which deletion would be trivial, yes). 

Hence, with the less is more approach, Go authors would probably not be keen on adding mode and more runtime functions ala len, cap, delete unless there was no other way. And "append" is kind of nice because it solves more than 1 use case. Your slice "delete" would solve *one* case and again that case can be done with append already.

BTW, before Go 1, the way to delete from a map, if I recall correctly, was 

m["key"] = Z, false   (Z being the zero value of the map's value types)

Now, aren't you glad we at least got delete for maps? :-)

[Péter Szilágyi]

On Wed, Mar 19, 2014 at 5:31 PM, DV <dimiter....@gmail.com> wrote:

In general, I'm not too happy with how deleting from a slice needs to happen, but there are a few reasons for it:

1. A slice's backing store is just an array. Deleting from an array is actually not trivial in *any* language that has the C definition of arrays - it involves memory allocation (sometimes), copying (most of the time)

2. Even if there was a delete convenience operation on slices (ala map's delete), it would be just a wrapper on append anyway - I can't think of any other way to do it for storage that is essentially a C-style array. 

A slice is a nice abstraction on top of an array - nothing else. It's *not* a linked list (in which deletion would be trivial, yes). 

Hence, with the less is more approach, Go authors would probably not be keen on adding mode and more runtime functions ala len, cap, delete unless there was no other way. And "append" is kind of nice because it solves more than 1 use case. Your slice "delete" would solve *one* case and again that case can be done with append already.

BTW, before Go 1, the way to delete from a map, if I recall correctly, was 

m["key"] = Z, false   (Z being the zero value of the map's value types)

Now, aren't you glad we at least got delete for maps? :-)

Lol, now I know why I waited 3 years before jumping on the Go bandwagon :D

 

[Dan Kortschak]

Then write a helper:

func delete(l []ListenerList, i int) []ListenerList {
return append(l[:i], l[i+1:]...)

[Dan Kortschak]

s/delete/sliceDelete/

[Dan Kortschak]

Or even "better", as a method. Sorry, I shouldn't write before coffee.

[Rasmus Schultz]

Okay, I read everyone's replies, and thank you all.

I then went and read the blog article about slices which answered a lot more questions than the book and other materials I've read.

I then spent half an hour juggling slices on the playground, getting more of a feel for it.

It makes more sense to me now. You're right, "deleting" from a slice doesn't even make sense - deleting from a slice isn't even a thing, because that's just not how this data structure works.

Given how this data structure does work, I think I figured out a more meaningful way to do what I need to do while using this data structure the way it was intended - and let me know if this sounds right or wrong?

So I need to loop over the list of listeners, and I'm expecting some are going to be removed.

Given that "deleting" a slice would require you to copy and reconstruct the entire thing every time, I'm thinking you might as well initialize a new slice before you start the iteration - assuming most items are going to stay (which they are) you can then simply allocate a size equal to the current number of listeners, then copy every recurring listener to the new slice as you go.

This should be a lot more efficient than a full copy for every delete?

As a further optimization, I could also keep a count of the number of once-listeners - if there are no once-listeners, we can skip copying and reconstruction, and just loop over the listeners, not expecting to make any changes.

So this will work, I think :-)

So once again, thank you for your patience and your help!

I still have to wonder though... it's great that Go has slices, and it seems like you can make some clever memory and computational optimizations that would not be possible with conventional data structures. But sometimes (and probably most times IRL) programmer hours are a lot more expensive than clockcycles - it really wouldn't suck to also have more traditional/convenient data structures, for those times when you have to be task-oriented and raw performance is secondary to, well, gettin' shit done... ;-)

[Dan Kortschak]

On Wed, 2014-03-19 at 22:13 -0500, Rasmus Schultz wrote:
> Given that "deleting" a slice would require you to copy and
> reconstruct the entire thing every time, I'm thinking you might as

> well initialize a new slice *before *you start the iteration -

> assuming most items are going to stay (which they are) you can then
> simply allocate a size equal to the current number of listeners, then
> copy every recurring listener to the new slice as you go.
>
> This should be a lot more efficient than a full copy for every delete?

If you are not concerned with the order of the elements in the slice,
you can do an efficient delete operation based on end swapping:

func (l ListenerList) delete(i int) ListenerList {
l[i], l[len(l)-1] = l[len(l)-1], Listener{} // Help the GC here.
return l[:len(l)-1]
}

[Rasmus Schultz]

No, the order is (or could be) important - it's going to depend on what you're doing. That's part of the reason my current solution doesn't work - it's using separate lists for once-listeners and many-listeners, which means I don't know what order they were added... that'll have to change too.

Thanks though :-)