Frage Entfernen und Hinzufügen von Elementen zum Array in GO lang


Ich habe 2 Arrays deklariert als: var input []string und var output []string .

Das Eingabearray wird anfänglich mit einigen IDs gefüllt. Ausgabearray ist NULL.

Nach jeder Iteration möchte ich ein zufälliges Element aus dem Eingabearray entfernen und es zum Ausgabearray hinzufügen.

Am Ende sind alle Elemente im Ausgabearray gleich wie im Eingabearray (aber mit unterschiedlicher Reihenfolge (Indizierung)).

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

Wenn ich das versuche, bekomme ich array out of bounds error.


5
2017-11-20 19:37


Ursprung


Antworten:


Für die output Array müssen Sie verwenden append oder weisen Sie ihm eine Anfangskapazität zu, die der Größe von entspricht input.

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

wäre meine Empfehlung, weil append verursacht eine Menge unnötiger Neuzuweisungen und Sie wissen bereits, welche Kapazität Sie benötigen, da es auf dem basiert input.

Die andere Sache wäre:

output = append(output, input[index])

Aber wie ich schon sagte, von dem, was ich beobachtet habe, wächst die exponentielle Kapazität an. Dies wird Basis 2 sein, wenn Sie nichts angegeben haben, was bedeutet, dass Sie mehrere unnötige Neuzuweisungen vornehmen werden, bevor Sie die gewünschte Kapazität erreichen.


11
2017-11-20 19:39



Sie können einige nützliche Tricks an finden Golang / ScheibeTricks.

Seit der Einführung der append eingebaut, die meisten Funktionen des container/vector Paket, das in Go 1 entfernt wurde, kann mit repliziert werden append und copy.

Hier sind die Vektormethoden und ihre Schnittmanipulationsanaloga:

AppendVector
a = append(a, b...)
Kopieren
b = make([]T, len(a))
copy(b, a)
// or
b = append([]T(nil), a...)
Schnitt
a = append(a[:i], a[j:]...)
Löschen
a = append(a[:i], a[i+1:]...)
// or
a = a[:i+copy(a[i:], a[i+1:])]
Löschen ohne die Reihenfolge zu erhalten
a[i] = a[len(a)-1] 
a = a[:len(a)-1]

HINWEIS Wenn der Typ des Elements a ist Zeiger oder eine Struktur mit Zeigerfeldern, die Garbage Collected sein müssen, die obigen Implementierungen von Cut und Delete habe ein Potenzial Speicherleck Problem: Einige Elemente mit Werten werden immer noch nach slice referenziert a und kann daher nicht gesammelt werden. Der folgende Code kann dieses Problem beheben:

Schnitt

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]

Löschen

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

Löschen ohne die Reihenfolge zu erhalten

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]
Erweitern
a = append(a[:i], append(make([]T, j), a[i:]...)...)
Erweitern
a = append(a, make([]T, j)...)
Einfügen
a = append(a[:i], append([]T{x}, a[i:]...)...)

HINWEIS Der Zweite append erstellt ein neues Segment mit seinem eigenen zugrunde liegenden Speicher und kopiert Elemente in a[i:] zu diesem Slice, und diese Elemente werden dann zurück in den Slice kopiert a (von der ersten append). Die Erstellung des neuen Slice (und damit des Speichermülls) und der zweiten Kopie kann durch einen alternativen Weg vermieden werden:

Einfügen

s = append(s, 0)
copy(s[i+1:], s[i:])
s[i] = x
Einfügevektor
a = append(a[:i], append(b, a[i:]...)...)
Pop
x, a = a[0], a[1:]
Pop zurück
x, a = a[len(a)-1], a[:len(a)-1]
drücken
a = append(a, x)
Drücken Sie vorne
a = append([]T{ x }, a...)
Verschiebung
x, a := a[0], a[1:]
Unscharf
a = append([]T{x}, a...)

Zusätzliche Tricks

Filterung ohne Zuteilung

Dieser Trick nutzt die Tatsache, dass ein Slice das gleiche Backing-Array und dieselbe Kapazität wie das Original hat, sodass der Speicher für das gefilterte Slice wiederverwendet wird. Natürlich werden die ursprünglichen Inhalte geändert.

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

Umkehrung

So ersetzen Sie den Inhalt eines Schnitts durch dieselben Elemente, jedoch in umgekehrter Reihenfolge:

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

Das gleiche, außer mit zwei Indizes:

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

Mischen

Fisher-Yates-Algorithmus:

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

-2
2018-01-18 12:19