Remove and adding elements to array in GO lang

huangapple go评论78阅读模式
英文:

Remove and adding elements to array in GO lang

问题

我有两个声明为var input []stringvar output []string的数组。

输入数组最初填充了一些ID。输出数组为空。

在每次迭代之后,我想从输入数组中随机删除一个元素,并将其添加到输出数组中。

最后,输出数组中的所有元素将与输入数组相同(但索引顺序不同)。

for index := 0; index < len(input); index++ {
    if !visited[index] {
        //做一些操作
    }
}
output[迭代索引] = input[当前索引]

当我尝试这样做时,我得到了"数组越界错误"。

英文:

I have 2 arrays declared as :
var input []string and var output []string .

The input array is filled with some IDs initially. Output array is NULL.

After every iteration I want to remove a random element from input array and add it to output array.

At the end all the elements in output array will be same as input array (but with different ordering(indexing)).

for index := 0; index &lt; len(input); index++ {
    if !visited[index] {
        //do something
    }
}
output[#iteration index] = input[current index]

When I try to do this, I get array out of bounds error.

答案1

得分: 51

对于output数组,你需要使用append函数或者在初始化时分配与input大小相匹配的初始容量。

在循环之前,我建议使用以下代码:

output := make([]string, len(input))

这是因为append函数会导致大量不必要的重新分配,而且你已经知道所需的容量,因为它基于input的大小。

另一种方法是:

output = append(output, input[index])

但正如我所说的,根据我的观察,append函数以指数方式增加初始容量。如果你没有指定任何容量,它将以2为底,这意味着在达到所需容量之前会进行多次不必要的重新分配。

英文:

For the output array you need to use append or allocate it with an initial capacity to match the size of input.

// before the loop
output := make([]string, len(input))

would be my recommendation because append causes a bunch of needless reallocations and you already know what capacity you need since it's based on the input.

The other thing would be:

output = append(output, input[index])

But like I said, from what I've observed append grows the initial capacity exponentially. This will be base 2 if you haven't specified anything which means you're going to be doing several unneeded reallocations before reaching the desired capacity.

答案2

得分: 43

你可以在golang/SliceTricks中找到一些有用的技巧。

自从引入了append内置函数后,大部分container/vector包的功能已经在Go 1中被移除,可以使用appendcopy来复制这些功能。

下面是向量方法及其切片操作的对应关系:

AppendVector

a = append(a, b...)

Copy

b = make([]T, len(a))
copy(b, a)
// 或者
b = append([]T(nil), a...)

Cut

a = append(a[:i], a[j:]...)

Delete

a = append(a[:i], a[i+1:]...)
// 或者
a = a[:i+copy(a[i:], a[i+1:])]

Delete without preserving order

a[i] = a[len(a)-1] 
a = a[:len(a)-1]

注意:如果元素的类型是指针或具有指针字段的结构体,需要进行垃圾回收,上述的CutDelete实现可能存在潜在的内存泄漏问题:一些具有值的元素仍然被切片a引用,因此无法被回收。以下代码可以解决这个问题:

> Cut

copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
    a[k] = nil // 或者类型T的零值
}
a = a[:len(a)-j+i]

> Delete

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // 或者类型T的零值
a = a[:len(a)-1]

> Delete without preserving order

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

Expand

a = append(a[:i], append(make([]T, j), a[i:]...)...)

Extend

a = append(a, make([]T, j)...)

Insert

a = append(a[:i], append([]T{x}, a[i:]...)...)

注意:第二个append创建了一个具有自己底层存储的新切片,并将a[i:]中的元素复制到该切片中,然后这些元素被复制回切片a(通过第一个append)。可以通过使用另一种方式来避免创建新切片(从而避免内存垃圾)和第二次复制:

> Insert

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

InsertVector

a = append(a[:i], append(b, a[i:]...)...)

Pop

x, a = a[0], a[1:]

Pop Back

x, a = a[len(a)-1], a[:len(a)-1]

Push

a = append(a, x)

Push Front

a = append([]T{ x }, a...)

Shift

x, a := a[0], a[1:]

Unshift

a = append([]T{x}, a...)

额外的技巧

无需分配内存进行过滤

这个技巧利用了切片与原始切片共享相同的底层数组和容量的特性,因此存储空间被重用用于过滤后的切片。当然,原始内容会被修改。

b := a[:0]
for _, x := range a {
    if f(x) {
        b = append(b, x)
    }
}

反转

将切片的内容替换为相同元素但顺序相反的内容:

for i := len(a)/2-1; i >= 0; i-- {
    opp := len(a)-1-i
    a[i], a[opp] = a[opp], a[i]
}

使用两个索引的方式:

for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
    a[left], a[right] = a[right], a[left]
}

洗牌

Fisher-Yates算法:

for i := len(a) - 1; i > 0; i-- {
    j := rand.Intn(i + 1)
    a[i], a[j] = a[j], a[i]
}
英文:

You could find some useful tricks at golang/SliceTricks.

Since the introduction of the append built-in, most of the functionality of the container/vector package, which was removed in Go 1, can be replicated using append and copy.

Here are the vector methods and their slice-manipulation analogues:

AppendVector

a = append(a, b...)

Copy

b = make([]T, len(a))
copy(b, a)
// or
b = append([]T(nil), a...)

Cut

a = append(a[:i], a[j:]...)

Delete

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

Delete without preserving order

a[i] = a[len(a)-1] 
a = a[:len(a)-1]

NOTE If the type of the element is a pointer or a struct with pointer fields, which need to be garbage collected, the above implementations of Cut and Delete have a potential memory leak problem: some elements with values are still referenced by slice a and thus can not be collected. The following code can fix this problem:

> Cut

copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k &lt; n; k++ {
    a[k] = nil // or the zero value of T
}
a = a[:len(a)-j+i]

> Delete

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

> Delete without preserving order

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

Expand

a = append(a[:i], append(make([]T, j), a[i:]...)...)

Extend

a = append(a, make([]T, j)...)

Insert

a = append(a[:i], append([]T{x}, a[i:]...)...)

NOTE The second append creates a new slice with its own underlying storage and copies elements in a[i:] to that slice, and these elements are then copied back to slice a (by the first append). The creation of the new slice (and thus memory garbage) and the second copy can be avoided by using an alternative way:

> Insert

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

InsertVector

a = append(a[:i], append(b, a[i:]...)...)

Pop

x, a = a[0], a[1:]

Pop Back

x, a = a[len(a)-1], a[:len(a)-1]

Push

a = append(a, x)

Push Front

a = append([]T{ x }, a...)

Shift

x, a := a[0], a[1:]

Unshift

a = append([]T{x}, a...)

Additional Tricks

Filtering without allocating

This trick uses the fact that a slice shares the same backing array and capacity as the original, so the storage is reused for the filtered slice. Of course, the original contents are modified.

b := a[:0]
for _, x := range a {
    if f(x) {
        b = append(b, x)
    }
}

Reversing

To replace the contents of a slice with the same elements but in reverse order:

for i := len(a)/2-1; i &gt;= 0; i-- {
    opp := len(a)-1-i
    a[i], a[opp] = a[opp], a[i]
}

The same thing, except with two indices:

for left, right := 0, len(a)-1; left &lt; right; left, right = left+1, right-1 {
    a[left], a[right] = a[right], a[left]
}

Shuffling

Fisher–Yates algorithm:

for i := len(a) - 1; i &gt; 0; i-- {
    j := rand.Intn(i + 1)
    a[i], a[j] = a[j], a[i]
}

答案3

得分: 0

在Go 1.21中,Slice提供了InsertDelete等函数。

示例

Insert

package main

import (
	"fmt"
	"slices"
)

func main() {
	names := []string{"Alice", "Bob", "Vera"}
	names = slices.Insert(names, 1, "Bill", "Billie")
	names = slices.Insert(names, len(names), "Zac")
	fmt.Println(names)
}

Delete

package main

import (
	"fmt"
	"slices"
)

func main() {
	letters := []string{"a", "b", "c", "d", "e"}
	letters = slices.Delete(letters, 1, 4)
	fmt.Println(letters)
}
英文:

In Go 1.21, Insert, Delete (and more!) functions are available for Slice

Example

Insert

package main

import (
	&quot;fmt&quot;
	&quot;slices&quot;
)

func main() {
	names := []string{&quot;Alice&quot;, &quot;Bob&quot;, &quot;Vera&quot;}
	names = slices.Insert(names, 1, &quot;Bill&quot;, &quot;Billie&quot;)
	names = slices.Insert(names, len(names), &quot;Zac&quot;)
	fmt.Println(names)
}

Delete

package main

import (
	&quot;fmt&quot;
	&quot;slices&quot;
)

func main() {
	letters := []string{&quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;, &quot;e&quot;}
	letters = slices.Delete(letters, 1, 4)
	fmt.Println(letters)
}

huangapple
  • 本文由 发表于 2015年11月21日 03:37:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/33834742.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定