英文:
Remove and adding elements to array in GO lang
问题
我有两个声明为var input []string
和var 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 < 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中被移除,可以使用append
和copy
来复制这些功能。
下面是向量方法及其切片操作的对应关系:
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]
注意:如果元素的类型是指针或具有指针字段的结构体,需要进行垃圾回收,上述的Cut
和Delete
实现可能存在潜在的内存泄漏问题:一些具有值的元素仍然被切片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 < 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 >= 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 < 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 > 0; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
答案3
得分: 0
在Go 1.21中,Slice提供了Insert、Delete等函数。
示例
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 (
"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)
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论