在GO语言中删除元素并将其添加到数组中

Question

我有2个数组声明为: var input []string和var output []string.

输入数组最初填充了一些ID.输出数组为NULL.

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

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

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

当我尝试这样做时,我明白了array out of bounds error.

Answer 1

对于output阵列,您需要使用append或分配初始容量以匹配大小input.

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

将是我的建议,因为append导致一堆不必要的重新分配,你已经知道你需要什么容量,因为它是基于input.

另一件事是:

output = append(output, input[index])

但就像我说的那样,从我观察到的追加量来看,初始容量呈指数增长.如果您没有指定任何意味着您在达到所需容量之前将要进行多次不需要的重新分配,那么这将是基数2.

Answer 2

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

由于引入了append内置功能container/vector，因此可以使用append和复制在Go 1中删除的大多数软件包功能copy。

以下是向量方法及其切片操作类似物：

AppendVector

a = append(a, b...)

复制

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

切

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

删除

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

删除但不保留订单

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

注意如果元素的类型是一个指针或指针字段，其需要被垃圾收集一个结构，上述实施方式Cut和Delete有潜在的存储器泄露的问题：其值的一些元素仍然由切片引用a并因此不能集。以下代码可以解决此问题：

切

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]

删除

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

删除但不保留订单

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

扩大

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

延伸

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

插入

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

注意第二个组件append使用其自己的基础存储创建一个新的片段a[i:]，并将元素复制到该片段中，然后将这些元素复制回该片段a（由第一个append）。可以通过使用另一种方法来避免新切片的创建（以及由此产生的内存垃圾）和第二个副本：

插入

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

插入向量

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

流行音乐

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

回弹

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

推

a = append(a, x)

向前推

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

转移

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

换档

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]
}