Comment supprimer efficacement des éléments d'une tranche dans Go ?

éditeur php Apple vous présente comment supprimer efficacement des éléments des tranches dans Go. Dans le langage Go, la suppression d'éléments dans une tranche est une opération courante. Cependant, en raison des caractéristiques des tranches, la suppression directe d'un élément peut entraîner une modification de la longueur de la tranche, affectant ainsi les opérations ultérieures. Afin de supprimer efficacement des éléments d'une tranche, nous pouvons utiliser les caractéristiques de la tranche et certaines fonctions intégrées pour y parvenir. Plusieurs méthodes couramment utilisées seront présentées en détail ci-dessous.

Contenu de la question

Il existe plusieurs façons de supprimer des éléments de tranche. Mais que se passe-t-il si j’ai une application qui traite beaucoup de tranches ? Les tranches Go sont bien optimisées pour l'ajout de nouveaux éléments, mais existe-t-il un moyen efficace de supprimer des éléments d'une tranche (non seulement pour la vitesse, mais également pour une mémoire optimisée).

Je connais la fonction slices.Delete introduite dans Go 1.21, mais en coulisses, elle utilise les techniques bien connues suivantes :

return append(s[:i], s[j:]...)

Il semble que le tableau sous-jacent ne soit pas réduit dans ce cas. C'est idéal pour la vitesse, mais que se passe-t-il si nous avons beaucoup d'éléments (comme 100 000 ou 1 M) et que nous les réduisons ensuite à très peu (comme seulement 10) ? Il semble qu'il n'y ait pas d'optimisations de mémoire comme celles utilisées pour augmenter la capacité des tranches.

Lorsque nous n'avons pas besoin de conserver l'ordre des éléments dans une tranche, nous pouvons utiliser la méthode suivante (aller sur le lien Playground) :

func sliceDel[S ~[]E, E any](s S, i, j int) S {
    lastIdx := len(s) - (j - i)
    copy(s[i:], s[lastIdx:])
    return s[:lastIdx]
}

C'est utile lorsque nous avons une grande tranche et un petit nombre d'éléments à supprimer (l'idée derrière cela est de copier un petit nombre d'éléments de tranche).

Concernant la mémoire, la capacité est la même dans les deux cas et ne sera pas réduite. Par exemple :

// Reduce slice almost to zero
    for i := 0; i < sliceSize/2-1; i++ {
        sl = sliceDel(sl, 0, 2)
    }
    fmt.Printf("len = %d, cap = %d", len(sl), cap(sl))
        // Output: len = 2, cap = 100000

    // Reduce slice almost to zero
    for i := 0; i < sliceSize/2-1; i++ {
        sl = slices.Delete(sl, 0, 2)
    }
    fmt.Printf("len = %d, cap = %d", len(sl), cap(sl))
        // Output: len = 2, cap = 100000

Alors, existe-t-il un moyen d'optimiser l'utilisation de la mémoire ? Par exemple, si la longueur d’une tranche est inférieure à la moitié de sa capacité, réduisez la capacité de moitié.

J'aimerais également savoir comment faire cela efficacement, comme une technique comme celle-ci s[:len(s):len(s)] (expression de tranche complète utilisée par slices.Clip) ne réduit pas le tableau sous-jacent - elle enregistre uniquement la nouvelle capacité dans la structure de tranche pour éviter d'ajouter new Remplace l'élément de tranche parent lorsque l'élément est attaché à une tranche enfant (comme mentionné dans cette proposition).

Solutions

Il n'y a pas de solution "généralement meilleure". Vous avez montré plusieurs approches dans votre question, chacune pouvant être meilleure que les autres pour un scénario spécifique.

Si vous êtes dans une situation comme celle-ci, lorsque vous souhaitez conserver quelques éléments parmi plusieurs, ne commencez même pas à supprimer ces éléments. Construisez une nouvelle tranche avec ces éléments. En plus d'être plus rapide, cela résout également définitivement le problème de mémoire.

Vous ne pouvez pas réduire l'utilisation de la mémoire en utilisant des expressions de tranche complètes autres que l'allocation et l'utilisation de nouvelles tranches. Tant qu'il y a une référence au tableau de sauvegarde, il ne sera pas réduit (du moins pas dans les versions actuelles de Go). Si vous rencontrez une situation dans laquelle un grand tableau de sauvegarde est alloué mais où seule une petite partie de celui-ci est utilisée, vous pouvez allouer une nouvelle tranche et copier manuellement les éléments pour permettre au grand tableau d'être récupéré.

Considérez également que si vous disposez d'une très grande tranche dont vous devrez peut-être supprimer de nombreux éléments, une tranche n'est peut-être pas la meilleure structure de données à utiliser. Par exemple, vous pouvez essayer d'utiliser une liste chaînée, ou même essayer une carte : la suppression d'éléments d'une liste chaînée ou d'une carte sera beaucoup plus rapide, et une carte fournira également des temps de recherche rapides (O(n)), comme indiqué ci-dessous.

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!