Quelles sont les méthodes d'expansion du langage go ?

Les méthodes d'expansion du langage Go incluent : 1. L'expansion de la tranche. Lorsque vous utilisez l'ajout pour ajouter des éléments à la tranche, si l'espace de la tranche est insuffisant, l'expansion de la tranche sera déclenchée. 2. L'expansion de la carte. Deux conditions déclenchent l'expansion de la carte : 1. Lorsque le facteur de charge est supérieur à 6,5, c'est-à-dire que le nombre moyen de paires clé-valeur stockées dans chaque compartiment atteint 6,5. 2. Lorsque le nombre de débordements est supérieur à 2^ ; 15, c'est-à-dire lorsque le nombre de débordements dépasse 32 768.

L'environnement d'exploitation de ce tutoriel : système Windows 7, GO version 1.18, ordinateur Dell G3.

Déclencheurs d'expansion de tranche

Lors de l'utilisation de

append

pour ajouter des éléments à Slice, si l'espace de tranche est insuffisant, l'expansion de tranche sera déclenchéeLe principe

L'expansion signifie en fait la réallocation d'une mémoire plus grande que l'original. Les données de tranche sont copiées dans la nouvelle tranche, puis renvoyées dans la nouvelle tranche, et les données sont ajoutées après expansion.

Mécanisme

Avant la V1.8 :

La sélection de la capacité d'extension suit les règles suivantes :

Si la capacité originale du Slice est inférieure à 1024, la nouvelle capacité du Slice sera étendue à 2 fois l'originale ;

Si la capacité Slice d'origine est supérieure à Equal to 1024, la nouvelle capacité Slice sera étendue à 1,25 fois l'originale

// 1.17及以前的版本中
// old指切片的旧容量, cap指期望的新容量
func growslice(old, cap int) int {
    newcap := old
    doublecap := newcap + newcap
    // 如果期望容量大于旧容量的2倍，则直接使用期望容量作为最终容量
    if cap > doublecap {
        newcap = cap
    } else {
        // 如果旧容量小于1024，则直接翻倍
        if old < 1024 {
            newcap = doublecap
        } else {
            // 每次增长大约1.25倍
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    // 这里忽略了对齐操作
    return newcap
}

Après la V1.8 :

La sélection de la nouvelle capacité d'extension suit les règles suivantes : (a un coefficient d'expansion plus lisse)

Si la capacité originale de la tranche est inférieure à 256, la nouvelle capacité de la tranche sera étendue à 2 fois la taille d'origine

Si la capacité originale de la tranche est supérieure ou égale à 256, la La nouvelle capacité de la tranche sera étendue à sa taille d'origine
• Nouvelle capacité = (capacité d'origine + 3*256)/4

• // 只关心扩容规则的简化版growslice
  func growslice(old, cap int) int {
      newcap := old
      doublecap := newcap + newcap
      if cap > doublecap {
          newcap = cap
      } else {
          const threshold = 256 // 不同点1
          if old < threshold {
              newcap = doublecap
          } else {
              for 0 < newcap && newcap < cap {
                  newcap += (newcap + 3*threshold) / 4 // 不同点2
              }
              if newcap <= 0 {
                  newcap = cap
              }
          }
      }
      return newcap
  }

  Extension de la carte

  Il y a deux conditions qui déclenchent l'expansion

   :
  charger facteur > 6,5, c'est-à-dire que le nombre moyen de paires clé-valeur stockées dans chaque compartiment atteint 6,5.
  Incrément
  • Expansion
    Lorsque le nombre de débordements > 2^15, c'est-à-dire lorsque le nombre de débordements dépasse 32768.
  Égal
  • Expansion/Réarrangement
    Remarque : La création de seaux de débordement n'appartient pas au mécanisme d'expansion

  Expansion incrémentielle

  Lorsque le facteur de charge est trop grand, un nouvel espace de seau est ouvert et le le nombre de buckets est le précédent 2 fois
  • Le nouvel espace est référencé par buckets, et l'ancien espace est référencé par oldbuckets
  Après cela, les données dans oldbuckets seront progressivement déplacées vers l'espace buckets nouvellement ouvert
  • Considérant que si la carte stocke des centaines de millions de valeurs-clés, une relocalisation unique entraînera un retard relativement important, Go adopte une stratégie de relocalisation progressive, c'est-à-dire que
  déclenchera une relocalisation à chaque accès à la carte, et à chaque fois. 2 paires clé-valeur sont déplacées
  .

  Une fois que toutes les paires clé-valeur des oldbuckets ont été déplacées, supprimez les oldbuckets. La figure suivante montre une carte contenant un bucket entièrement chargé (pour faciliter la description, la zone de valeur du bucket est omise dans la figure) :

  La carte actuelle stocke 7 paires clé-valeur et seulement 1 seau. À l'heure actuelle, le facteur de charge est de 7 > 6,5. Lorsque les données sont à nouveau insérées, l'opération expansion

  sera déclenchée. Après

  expansion, la nouvelle clé d'insertion sera écrite dans le nouveau compartiment. Notez que parce que le facteur de charge est déclenché, le compartiment de débordement n'est pas créé Lorsque la 8ème paire clé-valeur est insérée, expansion

  sera déclenchée. Le diagramme schématique après

  expansion est le suivant :

  . Les opérations d'accès ultérieures à la carte déclencheront la migration et déplaceront progressivement les paires clé-valeur dans les anciens compartiments.

  Le diagramme une fois la migration terminée est le suivant :

  Pendant le processus de migration des données, les paires clé-valeur du compartiment d'origine existeront devant le nouveau compartiment et les paires clé-valeur nouvellement insérées existera à l'arrière du nouveau seau.

  Expansion/Réarrangement

  La soi-disant expansion

  égale ne signifie pas en fait une augmentation de la capacité. Le nombre de seaux reste inchangé. Nous devons refaire l'action de relocalisation similaire à une

  expansion incrémentielle et la supprimer. les clés libres. Les paires de valeurs sont réorganisées de manière à ce que le compartiment soit utilisé plus efficacement, garantissant ainsi un accès plus rapide. Dans des scénarios extrêmes, tels que des ajouts et des suppressions constants, et des paires clé-valeur concentrées dans un petit nombre de compartiments, cela entraînera une augmentation du nombre de compartiments de débordement, mais le facteur de charge n'est pas élevé, ce qui rend impossible l'exécution. relocalisation incrémentielle, comme suit Comme le montre l'image :
  

  Comme on peut le voir sur l'image ci-dessus, la plupart des seaux de trop-plein sont vides et l'efficacité de l'accès sera très mauvaise. À ce stade, une expansion égale est effectuée, c'est-à-dire que le nombre de compartiments reste inchangé. Après la réorganisation, le nombre de compartiments de débordement sera réduit, ce qui permet d'économiser de l'espace et d'améliorer l'efficacité de l'accès.

  【Recommandations associées :

  Tutoriel vidéo Go, Enseignement de la programmation

  】

  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!