Wie kann ich Subset-Beziehungen in Go mithilfe von Integer-Slices effizient bestimmen?

Effiziente Überprüfung von Teilmengenbeziehungen mit ganzzahligen Slices in Go

Die Feststellung, ob ein Slice eine Teilmenge eines anderen ist, ist eine häufige Rechenaufgabe. In Go gibt es verschiedene Ansätze, um dies zu erreichen, die unterschiedliche Effizienzniveaus bieten.

Eine einfache Methode besteht darin, über die Elemente beider Slices zu iterieren und jedes Element im kleineren Slice mit den Elementen im größeren Slice zu vergleichen . Aufgrund der iterativen Natur der Prüfung kann dieser Ansatz jedoch für große Slices rechenintensiv sein.

Es gibt einen alternativen Ansatz, der eine Kartendatenstruktur nutzt, um eine höhere Effizienz zu erreichen. Dieser Ansatz nutzt die Set-Differenz-Eigenschaft, bei der die Elemente des kleineren Slice vom größeren Slice subtrahiert werden, um zu bestimmen, ob noch Elemente übrig sind.

So implementieren Sie diesen Ansatz in Go:

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
func subset(first, second []int) bool {
    set := make(map[int]int)
    for _, value := range second {
        set[value] += 1
    }

    for _, value := range first {
        if count, found := set[value]; !found {
            return false
        } else if count < 1 {
            return false
        } else {
            set[value] = count - 1
        }
    }

    return true
}

func main() {
    fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

In dieser Implementierung wird eine Karte verwendet, um die Elemente des größeren Slice und ihre entsprechenden Anzahlen zu speichern. Die Iteration über die Elemente des kleineren Slice erfordert den Zugriff auf die Zählwerte in der Karte und deren Dekrementierung. Wenn im kleineren Slice ein fehlendes Element gefunden wird (nicht in der Karte gefunden) oder wenn die Anzahl unter 0 fällt (was darauf hinweist, dass im größeren Slice weniger Elemente vorhanden sind als im kleineren), gibt die Funktion „false“ zurück, was darauf hinweist, dass dies im kleineren Slice nicht der Fall ist eine Teilmenge. Die zeitliche Komplexität dieses Ansatzes ist deutlich geringer als beim iterativen Ansatz, was ihn für große Slices effizienter macht.

Das obige ist der detaillierte Inhalt vonWie kann ich Subset-Beziehungen in Go mithilfe von Integer-Slices effizient bestimmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!