Los: Anhängen, wenn eindeutig

75

Gibt es eine Möglichkeit, Slices / Maps auf das Vorhandensein eines Werts zu überprüfen?

Ich möchte einem Slice nur dann einen Wert hinzufügen, wenn er im Slice nicht vorhanden ist.

Das funktioniert, aber es scheint ausführlich. Gibt es einen besseren Weg, dies zu tun?

orgSlice := []int{1, 2, 3}
newSlice := []int{}
newInt := 2

newSlice = append(newSlice, newInt)
for _, v := range orgSlice {
    if v != newInt {
        newSlice = append(newSlice, v)
    }
}

newSlice == [2 1 3]
Kyle Finley
quelle
1
Betreff: BEARBEITEN - es ist die gleiche Geschichte für jeden gültigen Kartenschlüsseltyp - welche Zeichenfolge ist.
zzzz
1
Betreff: EDIT2 - Wenn die Reihenfolge der Werte in 'newSlice' keine Rolle spielt UND sie mithilfe einer Bereichsanweisung verwendet / verbraucht werden, ist ihre Konstruktion redundant - reichen Sie einfach die Schlüssel von 'set'.
zzzz
@jnml Danke für deine Kommentare. Ich speichere die Liste intsim GAE-Datenspeicher und zum Abfragen muss es sich um ein Slice ( []int) handeln. Macht diese Anforderung meine anfängliche Technik zur besseren Wahl? Die Listen werden klein sein.
Kyle Finley
3
Sie können die Verwendung von append()(und alle Neuzuweisungen) vermeiden , indem Sie zunächst eine erstellen newslice := make([]int, len(set)). Wenn Sie viele solcher "enthält den Schlüssel ..." - Tests durchführen (mindestens mehr als 2), ist die Konvertierung des Slice in eine Map [int] struct {} wahrscheinlich viel schneller, wenn Sie nur wenige Loops durchführen durch die Scheibe direkt ist wohl besser.
Tux21b
@ tux21b Ok, danke, ich weiß es wirklich zu schätzen, dass Sie sich die Zeit genommen haben, all dies zu erklären.
Kyle Finley

Antworten:

108

Ihr Ansatz würde für jede Einfügung eine lineare Zeit in Anspruch nehmen. Ein besserer Weg wäre, a zu verwenden map[int]struct{}. Alternativ können Sie auch ein map[int]booloder ähnliches verwenden, aber das Leere struct{}hat den Vorteil, dass es keinen zusätzlichen Platz belegt. Daher map[int]struct{}ist eine beliebte Wahl für eine Reihe von ganzen Zahlen.

Beispiel:

set := make(map[int]struct{})
set[1] = struct{}{}
set[2] = struct{}{}
set[1] = struct{}{}
// ...

for key := range(set) {
  fmt.Println(key)
}
// each value will be printed only once, in no particular order


// you can use the ,ok idiom to check for existing keys
if _, ok := set[1]; ok {
  fmt.Println("element found")
} else {
  fmt.Println("element not found")
}
tux21b
quelle
1
Danke für Ihre Antwort. Ein paar Fragen: Wie würden Sie dann das Slice neu erstellen? Gibt es eine Möglichkeit, diese Strategie mit Strings zum Laufen zu bringen? Entschuldigung, wenn diese offensichtlich sind - ich bin neu bei Go.
Kyle Finley
4
Ich würde nur die Karte während der Berechnung verwenden (weil sie ein O (1) -Verhalten anstelle von O (n) hat). Danach können Sie ein Slice erstellen und jeden Wert aus der Karte kopieren. Die Elemente haben danach eine zufällige Reihenfolge, daher möchten Sie sie möglicherweise sortieren. Und Sie können int, float, struct, string und arrays als Map-Schlüssel verwenden (zumindest in Go1).
Tux21b
1
Vielen Dank, dass Sie dargelegt haben, dass leere Strukturen keinen zusätzlichen Platz beanspruchen. Ich wusste das nicht und würde map [type] interface {} verwenden und der Schnittstelle null zuweisen.
user1943442
Ich habe auch die Methode map [type] interface {} verwendet. Nimmt dies nicht auch zusätzlichen Platz in Anspruch?
William King
39

Am effizientesten ist es wahrscheinlich, über das Slice zu iterieren und es anzuhängen, wenn Sie es nicht finden.

func AppendIfMissing(slice []int, i int) []int {
    for _, ele := range slice {
        if ele == i {
            return slice
        }
    }
    return append(slice, i)
}

Es ist einfach und offensichtlich und wird für kleine Listen schnell sein.

Außerdem ist es immer schneller als Ihre aktuelle kartenbasierte Lösung. Die kartenbasierte Lösung iteriert über das gesamte Segment, egal was passiert. Diese Lösung wird sofort zurückgegeben, wenn festgestellt wird, dass der neue Wert bereits vorhanden ist. Beide Lösungen vergleichen Elemente, während sie iterieren. (Jede Kartenzuweisungsanweisung führt sicherlich intern mindestens einen Kartenschlüsselvergleich durch.) Eine Karte wäre nur dann nützlich, wenn Sie sie über viele Einfügungen hinweg pflegen könnten. Wenn Sie es bei jeder Einfügung neu erstellen, gehen alle Vorteile verloren.

Wenn Sie wirklich große Listen effizient bearbeiten müssen, sollten Sie die Listen in sortierter Reihenfolge verwalten. (Ich vermute, die Reihenfolge spielt für Sie keine Rolle, da Ihre erste Lösung am Anfang der Liste und Ihre neueste Lösung am Ende angehängt wird.) Wenn Sie die Listen immer sortiert halten, können Sie die Funktion sort.Search verwenden Führen Sie effiziente binäre Einfügungen durch.

Sonia
quelle
19
"Die kartenbasierte Lösung iteriert über das gesamte Segment, egal was passiert" - sind Sie sicher, dass Hash-Maps so funktionieren?
Ottokar
@ Ottokar, ist er falsch? Viele Leute stimmten zu, aber es blieb keine Antwort übrig.
Filip Bartuzi
8
@FilipBartuzi Eigentlich glaube ich, dass ich die Bedeutung dieser Aussage falsch verstanden habe. Hash-Maps iterieren offensichtlich nicht über Elemente, um den Schlüssel zu finden, aber die "kartenbasierte Lösung" zum "Anhängen an Slice, wenn eindeutig" verliert ihren Vorteil, wenn wir das Slice in Map und dann die Map zurück in Slice konvertieren müssen .
Ottokar
0

Unterscheiden eines Arrays einer Struktur:

func distinctObjects(objs []ObjectType) (distinctedObjs [] ObjectType){
        var output []ObjectType
    for i:= range objs{
        if output==nil || len(output)==0{
            output=append(output,objs[i])
        } else {
            founded:=false
            for j:= range output{
                    if output[j].fieldname1==objs[i].fieldname1 && output[j].fieldname2==objs[i].fieldname2 &&......... {
                    founded=true
                }
            }
            if !founded{
                output=append(output,objs[i])
            }
        }
    }
    return output
}

wo die Struktur hier so etwas ist wie:

type ObjectType struct {
    fieldname1 string
    fieldname2 string
    .........
}

Das Objekt wird hier durch markierte Felder unterschieden:

if output[j].fieldname1==objs[i].fieldname1 && output[j].fieldname2==objs[i].fieldname2 &&......... {
Bisschen
quelle
-1
package main

import (
    "fmt"
    "os"
    "reflect"
)

func main() {
/*  s := []string{"a", "b"}
    fmt.Println(s)

    s = AppendIfMissing(s, "4").([]string)

    fmt.Println(s)*/

/*  var a []*string
    a = make([]*string, 0)
    e := "4"
    a = AppendIfMissing(a, &e).([]*string)
    fmt.Println(*a[0])*/

    var a []*float64
    a = make([]*float64, 3)
    e := 4.4
    d := 4.41
    a = AppendIfMissing(a, &e).([]*float64)
    a = AppendIfMissing(a, &d).([]*float64)
    fmt.Println(*a[3], *a[4])
}

func AppendIfMissing(array interface{}, element interface{}) interface{} {
    if reflect.ValueOf(array).IsNil() {
        fmt.Fprintf(os.Stderr, "array not initialized\n")
        return nil
    }

    switch reflect.TypeOf(array).Kind() {
    case reflect.Slice:
        arrayV := reflect.ValueOf(array)
        arrayVLen := arrayV.Len()
        if arrayVLen == 0 {//if make len == 0
            sliceNew := reflect.MakeSlice(reflect.ValueOf(array).Type(), 1, 1)
            if sliceNew.Index(0).Type() != reflect.ValueOf(element).Type() {
                fmt.Fprintf(os.Stderr, "types are not same\n")
                return sliceNew.Interface()
            }

            sliceNew.Index(0).Set(reflect.ValueOf(element))
            return sliceNew.Interface()
        }
        for i := 0; i < arrayVLen; i++ {
            if i == 0 && reflect.ValueOf(element).Kind() != arrayV.Index(i).Kind() {
                fmt.Fprintf(os.Stderr, "types are not same\n")
                return array
            }
            if arrayV.Index(i).Interface() == element {
                return array
            }
        }
    default:
        fmt.Fprintf(os.Stderr, "first element is not array\n")
        return array
    }

    arrayV := reflect.ValueOf(array)
    elementV := reflect.ValueOf(element)
    appendAE := reflect.Append(arrayV, elementV)

    return appendAE.Interface()
}
book777
quelle