Re: [go-nuts] Why not provide a delete function in slices just like in maps?

607 views
Skip to first unread message

Rob Pike

unread,
Jun 6, 2013, 9:09:13 AM6/6/13
to houshu...@pinidea.com, golan...@googlegroups.com
First, the implementation of "delete from slice" would be exactly the
same as the implementation of
slice = append(slice[:i], slice[i+1:]...)
Second, append only allocates when there isn't room. Since deleting
doesn't require more space, this is not an allocating operation.

In short, the code you're complaining about is optimal in everything
except possibly keystrokes. Far beyond human logic, perhaps, but
computers have their own cold logic.

-rob

Jan Mercl

unread,
Jun 6, 2013, 9:09:48 AM6/6/13
to houshu...@pinidea.com, golang-nuts
On Thu, Jun 6, 2013 at 10:13 AM, <houshu...@pinidea.com> wrote:
> When you need to remove something from a slice, the only thing you can do
> now is:
>
> slice = append(slice[:i], slice[i+1:]...)
>
> This is stupid because it's far beyond human logic: Why I need to make a new
> slice every time instead of just simply remove an element from the old one??

Absolutely no new slice instance is being made here. The existing
instance gets a new value, which is a three word struct.

> There is also another potential bug: if i+1>len(slice), it will cause panic.
> So you need to check it every time, which is also ridiculous.

Have you ever actually tried it? http://play.golang.org/p/IAR3xOJUEk

-j

James Bardin

unread,
Jun 6, 2013, 9:24:59 AM6/6/13
to golan...@googlegroups.com, houshu...@pinidea.com

and even more convincing...

Sebastien Binet

unread,
Jun 6, 2013, 9:32:36 AM6/6/13
to Rob Pike, houshu...@pinidea.com, golan...@googlegroups.com
Rob,

On Thu, Jun 6, 2013 at 3:09 PM, Rob Pike <r...@golang.org> wrote:
> First, the implementation of "delete from slice" would be exactly the
> same as the implementation of
> slice = append(slice[:i], slice[i+1:]...)
> Second, append only allocates when there isn't room. Since deleting
> doesn't require more space, this is not an allocating operation.

true.
and I suppose one gets used to this slice trick (which is indeed
referenced on the corresponding wiki page[0])

that said, it stands to reason to consider making the 'delete' builtin
function overloaded for slices too.
ie:
func delete( []T, int )
func delete(map[T]U, T)

-s

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

Frithjof Schulze

unread,
Jun 6, 2013, 9:33:12 AM6/6/13
to golan...@googlegroups.com
One can even do something like http://play.golang.org/p/IabKrc40eK

Does the spec actually guarantee that this will work?


--
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/groups/opt_out.
 
 

Péter Szilágyi

unread,
Jun 6, 2013, 9:36:23 AM6/6/13
to Frithjof Schulze, golang-nuts
I think this clause covers it:

"A slice therefore shares storage with its array and with other slices of the same array"

Matthew Kane

unread,
Jun 6, 2013, 9:36:59 AM6/6/13
to houshu...@pinidea.com, golang-nuts
If you don't need to preserve order, you can swap the item to be deleted, then shorten the slice by 1. This saves the work of moving every element over.

func delete(aslice []T, index int) outslice []T {
    var zero T
    aslice[index], aslice[len(aslice)-1] = aslice[len(aslice)-1], zero
    outslice = aslice[:len(aslice)-2]
    return outslice
}



On Thu, Jun 6, 2013 at 4:13 AM, <houshu...@pinidea.com> wrote:
When you need to remove something from a slice, the only thing you can do now is:

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

This is stupid because it's far beyond human logic: Why I need to make a new slice every time instead of just simply remove an element from the old one??

There is also another potential bug: if i+1>len(slice), it will cause panic. So you need to check it every time, which is also ridiculous.

So why not just simply provide a safe "delete" function just like in map? 

If there is any reason not to do it, please let us know.

These words might seems offensive, but I was really annoyed about this problem for a long time, forgive me.

--
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/groups/opt_out.
 
 



--
matt kane
twitter: the_real_mkb / nynexrepublic
http://hydrogenproject.com

chris dollin

unread,
Jun 6, 2013, 9:37:23 AM6/6/13
to houshu...@pinidea.com, golang-nuts
On 6 June 2013 09:13, <houshu...@pinidea.com> wrote:
When you need to remove something from a slice, the only thing you can do now is:

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

... removing the element with index i ...

This is stupid because it's far beyond human logic:

Oh, come on. "Everything before the element I want to remove, then
everything after it stuck on the end."

Why I need to make a new slice every time instead of just simply remove an element from the old one??

No matter how you do it, you'll end up with a new slice value. (That
value gets stored into the same space as the original slice -- no extra
allocation is needed.)

There is also another potential bug: if i+1>len(slice), it will cause panic. So you need to check it every time, which is also ridiculous.

Um, no. If i-1 > len(slice) then i >= len(slice) and so isn't the index of
any element in the slice, so you've made a mistake in trying to remove
"it".

So why not just simply provide a safe "delete" function just like in map? 

You can do it using reslice and append. You can't do that with maps,
so the deletion operation is built-in.

Chris

--
Chris "allusive" Dollin

Frithjof Schulze

unread,
Jun 6, 2013, 10:31:57 AM6/6/13
to Péter Szilágyi, golang-nuts
Yes. But I was never sure if this has to be interpreted as "a slice might share storage" or
as "unless you append something beyond the capacity of a slice we guarantee that the slices will share storage in this particular way."

Reck Hou

unread,
Jun 6, 2013, 10:41:16 AM6/6/13
to golan...@googlegroups.com, houshu...@pinidea.com
I've read http://stackoverflow.com/questions/5020958/go-what-is-the-fastest-cleanest-way-to-remove-multiple-entries-from-a-slice, there seems to be so many solutions about this problem, and many newbie programmers are wondering if there's any built-in function to solve this problem.

So a built-in delete function like "delete_at"(remove element at index(x)) or "delete"(remove all elements in sliceA which exists in sliceB) like Ruby or Javascript is convenient. Programmers have to built their own delete function to do the trick for now.

Jesse McNelis

unread,
Jun 6, 2013, 10:41:34 AM6/6/13
to Sebastien Binet, golan...@googlegroups.com
On Thu, Jun 6, 2013 at 11:32 PM, Sebastien Binet <seb....@gmail.com> wrote:
> that said, it stands to reason to consider making the 'delete' builtin
> function overloaded for slices too.
> ie:
> func delete( []T, int )
> func delete(map[T]U, T)

For a map this does what it says and has constant cost.
For a slice this does a lot of unrelated copying and changes the
position of everything in a slice following this element and has a
cost related to the position of the element you're deleting.

The append() version makes this obvious. The delete() hides this.


--
=====================
http://jessta.id.au

Jan Mercl

unread,
Jun 6, 2013, 10:45:04 AM6/6/13
to Reck Hou, golang-nuts, houshu...@pinidea.com
On Thu, Jun 6, 2013 at 4:41 PM, Reck Hou <rec...@gmail.com> wrote:
> So a built-in delete function like "delete_at"(remove element at index(x))
> or "delete"(remove all elements in sliceA which exists in sliceB) like Ruby
> or Javascript is convenient. Programmers have to built their own delete
> function to do the trick for now.

Which of the two delete strategies (copy vs swap, ie. order preserving
or not) should be used for the new/proposed built-in? One of them
keeps an invariant at O(N). The other is O(1). Both of them are
correct in some situations and not correct in others. Which one _you_
would build into the language?

-j

Robert Johnstone

unread,
Jun 6, 2013, 1:24:48 PM6/6/13
to golan...@googlegroups.com, Sebastien Binet, jes...@jessta.id.au
The proposal from the OP has limited merit, but this argument is also pretty silly.  You might as well take a copy of the generated assembly code, and complain about all the details that are hidden no matter what the expression.  A look at the implementation for interface conversions will reveal that some operations in the language involve quite a lot of work behind the scenes.

John Nagle

unread,
Jun 6, 2013, 2:05:51 PM6/6/13
to golan...@googlegroups.com
This is a situation in which a list collection type (like C++),
or some efficient representation with multiple pieces chained together,
(like some string languages) would be useful. With those
representations, deletions in the middle of a sequence are cheap.

John Nagle


Thomas Bushnell, BSG

unread,
Jun 6, 2013, 2:08:05 PM6/6/13
to John Nagle, golang-nuts


John Nagle

unread,
Jun 6, 2013, 2:17:59 PM6/6/13
to Thomas Bushnell, BSG, golang-nuts
On 6/6/2013 11:08 AM, Thomas Bushnell, BSG wrote:
> What an excellent idea!
>
> http://golang.org/pkg/container/list/

That's interface-based, so each item gets inflated by
an interface item, which doubles the number of allocations
required. You also have to do the downcasting thing
to get elements out. "List" is a low-enough level concept
that it shouldn't be burdened with such overhead.

John Nagle

Thomas Bushnell, BSG

unread,
Jun 6, 2013, 2:26:06 PM6/6/13
to John Nagle, golang-nuts
You can also simply use pointers.

type myobject struct {
  field1 type1
  field2 type2
  next *myobject
  prevp **myobject
}

var mylist *myobject

Insert at front is
foo.next = mylist
foo.prevp = &mylist
mylist = foo

Delete is just
*foo.prevp = foo.next

If you want to be able to insert at the end, you do
var mylistTail = &mylist

And then
foo.next = *mylistTail
foo.prevp = mylistTail
*mylistTail = foo
mylistTail = &foo.next

I don't think there's a need for a primitive type for this, since it doesn't have any of the subtlety of maps.

Bob Hutchison

unread,
Jun 6, 2013, 3:19:24 PM6/6/13
to Rob Pike, houshu...@pinidea.com, golan...@googlegroups.com
As long as we remember about this: http://blog.golang.org/go-slices-usage-and-internals#TOC_6. (that '.' is part of the URL)

Bob

>
> -rob

John Nagle

unread,
Jun 6, 2013, 11:06:15 PM6/6/13
to golan...@googlegroups.com
On 6/6/2013 11:26 AM, Thomas Bushnell, BSG wrote:
> You can also simply use pointers.
>
> type myobject struct {
> field1 type1
> field2 type2
> next *myobject
> prevp **myobject
> }
>
> var mylist *myobject
>
> Insert at front is
> foo.next = mylist
> foo.prevp = &mylist
> mylist = foo
>
> Delete is just
> *foo.prevp = foo.next
....
It's 2013. Programmers should not have to write their own list
manipulation primitives for each type. That's so last-cen.

If Go isn't going to have user-defined parametrized types, a
few more built-in ones would be useful. At least the common
collection types for which "range" is a meaningful concept
should be supported.

John Nagle

Thomas Bushnell, BSG

unread,
Jun 6, 2013, 11:33:15 PM6/6/13
to John Nagle, golang-nuts

Oh, so this is a rant about generics. OK.

I don't write those as functions or primitives, any more than I write increment as a function. YMMV.

Thomas

Reply all
Reply to author
Forward
0 new messages