Question Est-il sécuritaire de supprimer les clés sélectionnées de la carte dans une boucle d'intervalle?


Comment peut-on supprimer les clés sélectionnées d'une carte? Est-il sécuritaire de combiner delete() avec plage, comme dans le code ci-dessous?

package main

import "fmt"

type Info struct {
    value string
}

func main() {
    table := make(map[string]*Info)

    for i := 0; i < 10; i++ {
        str := fmt.Sprintf("%v", i)
        table[str] = &Info{str}
    }

    for key, value := range table {
        fmt.Printf("deleting %v=>%v\n", key, value.value)
        delete(table, key)
    }
}

https://play.golang.org/p/u1vufvEjSw


81
2018-04-22 20:52


origine


Réponses:


C'est sûr! Vous pouvez également trouver un échantillon similaire dans Go efficace:

for key := range m {
    if key.expired() {
        delete(m, key)
    }
}

Et la spécification de langue:

L'ordre des itérations sur les mappes n'est pas spécifié et il n'est pas garanti qu'il soit identique d'une itération à l'autre. Si des entrées de carte non encore atteintes sont enlevé pendant l'itération, les valeurs d'itération correspondantes ne seront pas produites. Si les entrées de la carte sont créé pendant l'itération, cette entrée peut être produite pendant l'itération ou peut être ignorée. Le choix peut varier pour chaque entrée créée et d'une itération à l'autre. Si la carte est nulle, le nombre d'itérations est 0.


108
2018-04-22 21:19



La réponse de Sebastian est exacte, mais je voulais savoir Pourquoi c'était sûr, donc j'ai fait quelques fouilles dans le Code source de la carte. Il semble sur un appel à delete(k, v), en gros, il définit simplement un drapeau (tout en changeant la valeur du nombre) au lieu de supprimer la valeur:

b->tophash[i] = Empty;

(Vide est une constante pour la valeur 0)

Ce que la carte semble faire est d’allouer un nombre défini de compartiments en fonction de la taille de la carte, qui augmente à mesure que vous effectuez des insertions au rythme de 2^B (de ce code source):

byte    *buckets;     // array of 2^B Buckets. may be nil if count==0.

Il y a donc presque toujours plus de compartiments alloués que vous en utilisez, et quand vous faites un range sur la carte, il vérifie que tophash valeur de chaque seau dans cette 2^B pour voir si elle peut sauter par-dessus.

Pour résumer, le delete dans un range est sûr parce que les données sont techniquement toujours là, mais quand il vérifie la tophash il voit qu'il peut simplement sauter dessus et ne pas l'inclure dans quelque range opération que vous effectuez. Le code source inclut même un TODO:

 // TODO: consolidate buckets if they are mostly empty
 // can only consolidate if there are no live iterators at this size.

Cela explique pourquoi en utilisant le delete(k,v) La fonction ne libère pas réellement la mémoire, mais la supprime de la liste des compartiments auxquels vous avez accès. Si vous voulez libérer la mémoire réelle, vous devez rendre la carte entière inaccessible pour que la récupération de la mémoire intervienne. Vous pouvez le faire en utilisant une ligne comme

map = nil

115
2018-04-22 22:37



Je me demandais si une fuite de mémoire pouvait se produire. J'ai donc écrit un programme de test:

package main

import (
    log "github.com/Sirupsen/logrus"
    "os/signal"
    "os"
    "math/rand"
    "time"
)

func main() {
    log.Info("=== START ===")
    defer func() { log.Info("=== DONE ===") }()

    go func() {
        m := make(map[string]string)
        for {
            k := GenerateRandStr(1024)
            m[k] = GenerateRandStr(1024*1024)

            for k2, _ := range m {
                delete(m, k2)
                break
            }
        }
    }()

    osSignals := make(chan os.Signal, 1)
    signal.Notify(osSignals, os.Interrupt)
    for {
        select {
        case <-osSignals:
            log.Info("Recieved ^C command. Exit")
            return
        }
    }
}

func GenerateRandStr(n int) string {
    rand.Seed(time.Now().UnixNano())
    const letterBytes = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

On dirait que GC libère la mémoire. Donc ça va.


3
2017-09-14 07:22



En bref, oui. Voir les réponses précédentes.

Et aussi ceci, de ici:

ianlancetaylor a commenté le 18 février 2015
  Je pense que la clé pour comprendre ceci est de réaliser que lors de l'exécution du corps d'une déclaration for / range, il n'y a pas d'itération en cours. Il y a un ensemble de valeurs qui ont été vues et un ensemble de valeurs qui n'ont pas été vues. Lors de l'exécution du corps, l'une des paires clé / valeur qui a été vue - la paire la plus récente - a été affectée à la ou aux variables de l'instruction range. Il n'y a rien de particulier à propos de cette paire clé / valeur, ce n'est que l'un de ceux qui ont déjà été vus pendant l'itération.

La question à laquelle il répond est de modifier les éléments de la carte en place range opération, c'est pourquoi il mentionne "l'itération actuelle". Mais cela est également pertinent ici: vous pouvez supprimer des clés pendant une plage, ce qui signifie simplement que vous ne les verrez plus plus tard dans la plage (et si vous les avez déjà vues, ça va).


0
2018-02-08 21:57