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

[Rob Pike]

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]

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]

and even more convincing...

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

[Sebastien Binet]

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]

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]

I think this clause covers it:

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

[Matthew Kane]

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]

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]

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]

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]

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]

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]

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]

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]

What an excellent idea!

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

[John Nagle]

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]

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]

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]

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]

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