delete from slice, without copying and pasting code?

[ChrisLu]

I am doing this to delete from a slice. However, the if I need to do this on a different slice type, e.g., []*Node, I have to copy the code for a different type. The generics-support question has been discussed many times and I don't want to go there. I just want to know what's a good way to handle this simple and frequent scenario: What's the best way to delete from slice, without copying and pasting code?

func deleteFromSlice(i int, slice []*Machine) []*Machine{

    switch i {

        case -1://do nothing

        case 0: slice = slice[1:]

        case len(slice)-1: slice = slice[:len(slice)-1]

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

    }

    return slice

}

Chris

[Steve McCoy]

Unfortunately, there is no general option that won't be more work than repeating the code.

There's another, quicker way to delete, if you don't care about the elements' order. You can copy the last element to position i and then shrink the slice:

slice[i] = slice[len(slice)-1]

slice = slice[:len(slice)-1]

[Peter S]

s = s[:i+copy(s[i:], s[i+1:])]

--
 
 

[yy]

On 18 September 2012 18:41, ChrisLu <chri...@gmail.com> wrote:
> func deleteFromSlice(i int, slice []*Machine) []*Machine{
> switch i {
> case -1://do nothing
> case 0: slice = slice[1:]
> case len(slice)-1: slice = slice[:len(slice)-1]
> default: slice = append(slice[:i], slice[i+1:]...)
> }
> return slice
> }

You don't need this switch.

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

also works when i is 0 or len(slice)-1


--
- yiyus || JGL .

[Jan Mercl]

On Tue, Sep 18, 2012 at 7:44 PM, Peter S <spete...@gmail.com> wrote:
> s = s[:i+copy(s[i:], s[i+1:])]

Hard to beat! ;-)

-j

[jorelli]

fwiw, there's more stuff like this on the slice tricks wiki page: http://code.google.com/p/go-wiki/wiki/SliceTricks

[Patrick Mylund Nielsen]

Hard to read *

-j

--

[Chris Lu]

Thanks for the previous answers and all of the one-liner tricks. It's very practical.

Chris

[Jan Mercl]

Would like to know why it's hard to read. Not arguing, honestly curious.

-j

[Job van der Zwan]

So, given these two options:

s = s[:i+copy(s[i:], s[i+1:])]

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

Am I correct in understanding the latter creates a new slice, whereas the former overwrites the original? What about the other slice tricks on the wiki mentioned by jorelli[1], do they also have counterparts using the copy builtin?

[1]  http://code.google.com/p/go-wiki/wiki/SliceTricks

[Jan Mercl]

On Tue, Sep 18, 2012 at 8:49 PM, Job van der Zwan
<j.l.van...@gmail.com> wrote:
> So, given these two options:
>
> s = s[:i+copy(s[i:], s[i+1:])]
>
> slice = append(slice[:i], slice[i+1:]...)
>
> Am I correct in understanding the latter creates a new slice, whereas the
> former overwrites the original?

No: http://play.golang.org/p/iqwKS8jd2C

Longer version:
- Yes. Both statements overwrite LHS with RHS which LSH is part of
(slice really is a value type).
- No. Both statements reuse the existing slice backing storage array
as the len is (only) shrinking (and cap is not affected at all).

-j

[Job van der Zwan]

Ah, I see now, thank you. So is there any difference under the hood, or should I just go with the less complicated append version in situations like this?

[bryanturley]

I find it hard to read to actually, but acceptable.
There are many symbols and my brain has to stop and process that line to understand it.
Don't make go perl please ;)   (no offense to perl lovers intended)

In reality slices aren't meant to be deleted from, if you are going to do frequent deletions from a (long) list you should probably used some form of linked list.
Though that might be overkill for simple array-like data which is why i do use similar slice tricks myself.

[Uriel]

On Tue, Sep 18, 2012 at 9:22 PM, bryanturley <bryan...@gmail.com> wrote:
>
> In reality slices aren't meant to be deleted from, if you are going to do
> frequent deletions from a (long) list you should probably used some form of
> linked list.
> Though that might be overkill for simple array-like data which is why i do
> use similar slice tricks myself.

Almost every time I have seen people using container/List or pretty
much container/*, it would have been better to use slices or maps or
chans or some other built in type, or building your own datastructure.

Go is like Java or C++, is much more like C, learn to use what the
language gives and usually you will find a clean, simple and efficient
solution.

Uriel

> On Tuesday, September 18, 2012 2:04:38 PM UTC-5, Jan Mercl wrote:
>>
>> On Tue, Sep 18, 2012 at 8:49 PM, Job van der Zwan
>> <j.l.van...@gmail.com> wrote:
>> > So, given these two options:
>> >
>> > s = s[:i+copy(s[i:], s[i+1:])]
>> >
>> > slice = append(slice[:i], slice[i+1:]...)
>> >
>> > Am I correct in understanding the latter creates a new slice, whereas
>> > the
>> > former overwrites the original?
>>
>> No: http://play.golang.org/p/iqwKS8jd2C
>>
>> Longer version:
>> - Yes. Both statements overwrite LHS with RHS which LSH is part of
>> (slice really is a value type).
>> - No. Both statements reuse the existing slice backing storage array
>> as the len is (only) shrinking (and cap is not affected at all).
>>
>> -j
>

> --
>
>

[bryanturley]

Yeah I personally have never used anything in the container package.
Mostly it is slices but in a few cases it was cleaner and definitely faster performance wise to implement a linked list or other more complicated data structures.
There is a reason we didn't use only malloc/memcpy to do lists in pure c.
I was just saying various slice tricks are not always the best answer.

[Jan Mercl]

On Tue, Sep 18, 2012 at 9:20 PM, Job van der Zwan
<j.l.van...@gmail.com> wrote:
> Ah, I see now, thank you. So is there any difference under the hood, or
> should I just go with the less complicated append version in situations like
> this?

I don't think there's a general answer to this. Depending on the
expectable slice length and possibly required/not required
ordering/positional invariants, the delete-by-moving-the-last-element
might be (far) superior in performance.

BTW: The just mentioned is IMO a good example/reason for not having a
builtin slice-delete. Compare that with any fancy
Delete/Remove/Expell/YouNameIt method of any
BigLangUltimateContainerObject. One should notice how much control is
lost with the one-approach-shall-fit-every-situation fallacy
"concept".

-j

[Ethan Burns]

On Tuesday, September 18, 2012 1:49:21 PM UTC-4, yiyus wrote:

Nice, however, is this guaranteed to always work correctly?  The spec is very explicit that copy() will behave as expected when the source and destination overlap, but I see no mention of how append() behaves when the capacity of the first slice overlaps the second slice.  I have been avoiding these situations, but if there is some kind of guarantee that it will always work then I would be happy to use this particular trick.

Best,

Ethan

[bryanturley]

I would say if your list is over a ~100Kbytes *AND* your code needs to run at it's fastest you shouldn't use slice tricks that may require you to move memory around, implement something else yourself.
And if you really really need performance even a single kilobyte is fairly large to be moving around.
No need to waste your fancy cpu cache and raw memory throughput.

On that subject does copy() use non-temporal writes where available?

[Kevin Gillette]

append does the equivalent of copy internally. If you think about it anyway, overlapping slices is not a problem, as long as you're appending the "later" (higher indexed) slice to the earlier one, since to copy n-byte chunk worth of information, you must first read n bytes of information -- a source byte cannot possibly be overwritten before its source byte is already copied, as long as the implementation is sane/straightforward, and does the copy in forward-order.

[Ethan Burns]

On Tuesday, September 18, 2012 5:02:25 PM UTC-4, Kevin Gillette wrote:

append does the equivalent of copy internally. If you think about it anyway, overlapping slices is not a problem, as long as you're appending the "later" (higher indexed) slice to the earlier one, since to copy n-byte chunk worth of information, you must first read n bytes of information -- a source byte cannot possibly be overwritten before its source byte is already copied, as long as the implementation is sane/straightforward, and does the copy in forward-order.

I agree, and a quick test can show that it works as expected in the current implementation, however, the spec makes no guarantees, and the explicit guarantee for copy() makes me a little afraid to assume any such guarantee about append().

Ethan

[Kyle Lemons]

Eh?  How so?  How could append be implemented that would cause it to break?  The spec explicitly says that it will be reallocated "if" it can't fit.  Since it clearly can fit, it won't be reallocated.  The slices are evaluated and passed before the append is evaluated, so the bounds aren't going to change.  It seems pretty guaranteed to me.

[Steve McCoy]

Well, how could copy() be implemented that would cause it to break? He's concerned with that scenario, not reallocating. The docs don't explicitly say that append is implemented with copy() or a copy equivalent, so he's worried about a memcpy/memmove-style situation.

[Kevin Gillette]

I don't think he's concerned with copy at all, but with the copy-like behavior append has when dealing with overlapping slices, since, according to him, the spec doesn't explicitly 'okay' overlapping appends the way it 'okays' uses of copy with overlapping slices.

[Kyle Lemons]

That's what I don't get... There is no overlap.

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

The ranges are clearly 0..i and i+1..end, no overlap.

--
 
 

[David Symonds]

On Wed, Sep 19, 2012 at 12:46 PM, Kyle Lemons <kev...@google.com> wrote:

> That's what I don't get... There is no overlap.
>
> a = append(a[:i], a[i+1:]...)
>
> The ranges are clearly 0..i and i+1..end, no overlap.

append is allowed to simply expand its first argument to make room for
the new elements (i.e. no new allocation), so in this case it's going
to be writing to a[:len(a)-1], and that overlaps with a[i+1:].

[Job van der Zwan]

Maybe he's worried about the implementation for copying doing something like:

for j := i; j < bla; j++ {

a[j] = s[j-1]

}

Under the hood for the case:

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

I dunno, just a wild guess. Anyway, that should be covered by the same rules that guarantee that i, j = j, i work as a swap, right?

[Job van der Zwan]

Errr... that should be:

for j := i; j < bla; j++ {

a[j] = a[j-1]

}

[yy]

On 18 September 2012 23:49, Ethan Burns <burns...@gmail.com> wrote:
> I agree, and a quick test can show that it works as expected in the current
> implementation, however, the spec makes no guarantees, and the explicit
> guarantee for copy() makes me a little afraid to assume any such guarantee
> about append().

The spec cannot guarantee anything when you pass two overlapping
slices to append because append does not take two slice arguments, as
copy does. append is a variadic function: its arguments are a slice
and the elements you want to append to that slice. There's no possible
overlapping. The fact that the elements are actually passed to append
as a slice is only an implementation detail, but it is not part of the
specification and therefore should not modify append behavior.

In my opinion as long as the spec guarantees that append adds the
elements to the slice you should not worry about where those elements
come from.

[Kevin Gillette]

If append wants to maintain consistency with user-defined variadics in Go, then that can't be an "implementation detail", since the variadic variable is indeed a slice. For go to construct a slice when passed in separate, self-contained arguments is reasonable and necessary. For go to pass in the same slice (backed by the same array) when passed in as `slicevar...`, is not only reasonable, but is the only sane way to do it (what if slicevar had 50k elements? a copy of the underlying array would be reckless). The only thing you have to do account for this when writing variadics is to never assume you're the only one with a reference to that slice (and that modifying the slice could ruin somebody else's day).

So yes, overlaps _can_ happen. I still don't think that's a problem.

[Kyle Lemons]

Ah, indeed...  In that case, I side with the people who think the spec should probably be amended to say that it's safe?