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
.
To remove the first element, call remove(s, 0), to remove the second, call remove(s, 1), and so on and so forth. Hm, not really. This: s[i] = s[len(s)-1] definitely copies the last element to the element at index i . Then, return s[:len(s)-1] returns the slice without the last element.
To add an element to a slice , you can use Golang's built-in append method. append adds elements from the end of the slice. The first parameter to the append method is a slice of type T . Any additional parameters are taken as the values to add to the given slice .
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.
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:
AppendVectora = 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...)
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)
}
}
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]
}
Fisher–Yates algorithm:
for i := len(a) - 1; i > 0; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With