Comment puis-je déterminer efficacement les relations de sous-ensembles en Go à l'aide de tranches entières ?

Vérifier efficacement les relations de sous-ensembles avec des tranches entières dans Go

Déterminer si une tranche est un sous-ensemble d'une autre est une tâche de calcul courante. Dans Go, il existe différentes approches pour y parvenir, offrant différents niveaux d'efficacité.

Une méthode simple consiste à parcourir les éléments des deux tranches, en comparant chaque élément de la plus petite tranche aux éléments de la plus grande tranche. . Cependant, cette approche peut être coûteuse en termes de calcul pour les grandes tranches en raison de la nature itérative de la vérification.

Il existe une approche alternative qui exploite une structure de données cartographiques pour obtenir une plus grande efficacité. Cette approche exploite la propriété de différence définie, où les éléments de la plus petite tranche sont soustraits de la plus grande tranche pour déterminer s'il reste des éléments.

Voici comment implémenter cette approche dans 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}))
}

Dans cette implémentation, une carte est utilisée pour stocker les éléments de la plus grande tranche et leurs décomptes correspondants. Itérer sur les éléments de la plus petite tranche implique d'accéder aux décomptes de la carte et de les décrémenter. Si un élément manquant est rencontré dans la plus petite tranche (introuvable sur la carte) ou si le nombre tombe en dessous de 0 (indiquant moins d'éléments dans la plus grande tranche que dans la plus petite), la fonction renvoie false, indiquant que la plus petite tranche n'est pas un sous-ensemble. La complexité temporelle de cette approche est nettement inférieure à celle de l'approche itérative, ce qui la rend plus efficace pour les grandes tranches.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!