cours_21.md

title: "Barnes-Hut et B-arbres"
date: "2023-05-12"

Le cours précédent

A quoi sert l'algorithme de Barnes-Hut?

. . .

• A accélérer la résolution du problème à
  n
  -corps avec la gravitation,
• si on peut vivre avec une réduction de précision.

Sur quelle structure de données se base l'algorithme?

• L'arbre quaternaire.

. . .

Quelle est l'idée générale?

. . .

• Si un groupe d'étoiles est suffisamment loin, on le modélise comme un corps unique situé en son centre de masse.
• Exemple: Si on simule plusieurs galaxies, on considère chaque galaxie comme un corps unique!
• Un arbre quaternaire est une structure parfaite pour regrouper les étoiles.

Le cas à 10 corps

::: columns

:::: {.column width=50%}

Illustration: le cas à 10 corps

::::

:::: {.column width=50%}

Problématique

• On veut calculer la force sur
  1
  .

::::

:::

. . .

::: columns

:::: {.column width=50%}

Illustration: le cas à 10 corps

::::

:::: {.column width=50%}

Résultat

• Calcul et somme des forces venant des
  9
  autre corps.

::::

:::

Le cas à 10 corps

::: columns

:::: {.column width=50%}

Réduction d'un groupe à un seul corps

::::

:::: {.column width=50%}

Idée

• On accélère le calcul en traitant un groupe comme un seul corps.
• Fonctionne uniquement si le groupe est assez loin.
• Autrement l'approximation est trop grossière.

::::

:::

Solution: l'arbre quaternaire

Corps célestes - arbre

• On omet les nœuds vides pour éviter la surcharge.
• La numérotation est:
  • 0: ID
  • 1: SD
  • 2: IG
  • 3: SG

Exemple d'insertion

::: columns

:::: {.column width=50%}

Insertion corps 1

::::

:::: {.column width=50%}

Arbre, niveau 1

• Quadrant ID.
• La feuille est vide, on insère.

::::

:::

Exemple d'insertion

::: columns

:::: {.column width=50%}

Insertion corps 2

::::

:::: {.column width=50%}

Arbre, niveau 1

• Quadrant SD.
• La feuille est vide, on insère.

::::

:::

Exemple d'insertion

::: columns

:::: {.column width=50%}

Insertion corps 3 (1/N)

::::

:::: {.column width=50%}

Arbre, niveau 1

• Quadrant SD.
• La feuille est prise par 2.

::::

:::

Exemple d'insertion

::: columns

:::: {.column width=50%}

Insertion corps 3 (2/N)

::::

:::: {.column width=50%}

Arbre, niveau 2

• On crée un nouveau nœud.
• Deux corps dans le nœud ID.
• On crée un nouveau nœud.

::::

:::

Exemple d'insertion

::: columns

:::: {.column width=50%}

Insertion corps 3 (3/N)

::::

:::: {.column width=50%}

Arbre, niveau 3

• 2 va dans ID.
• 3 va dans SG.
• C'est des feuilles vides, tout va bien.

::::

:::

Exemple d'insertion

::: columns

:::: {.column width=50%}

Que fait-on avec les nœuds intérieurs?

• On les utilise pour:
  • stocker la masse totale;
  • stocker le centre de masse.

\begin{align} m&=m_2+m_3,\ \vec x &= \frac{m_2\vec x_2+m_3\vec x_3}{m}. \end{align}

Chaque feuille contient une étoile

::::

:::: {.column width=50%}

Arbre

::::

:::

Résumé

• Insertion du corps c dans le nœud n en partant de la racine.
• Si le nœud n
  • ne contient pas de corps, on y dépose c,
  • est interne, on met à jour masse et centre de masse. c est inséré récursivement dans le bon quadrant.
  • est externe, on subdivise n, on met à jour la masse et centre de masse, on insère récursivement les deux nœuds dans les quadrants appropriés.

Remarque

• Il faut stocker les coordonnées des quadrants.
• Un nœud a un comportement différent s'il est interne ou externe.

Algorithme d'insertion

Structure de données

struct node
    etoile e // externe: pour stocker 
    etoile sup_etoile // interne: pour stocker m, x
    quadrant q  // coordonnées du quadrant
    node enfants[4]

Remarque:

• On fait une simplification "moche": sup_etoile pourrait juste avoir une masse et une position.

Algorithme d'insertion

\footnotesize

Algorithme d'insertion, pseudo-code (15min, matrix)

. . .

rien insertion_etoile(arbre, e)  
    si (!est_vide(arbre) && dans_le_quadrant(arbre.q, e.x)) {
        si (est_feuille(arbre))
            si (!contient_etoile(arbre))
                arbre.e = e
            sinon
                // on crée enfants et arbre.sup_etoile est initialisée
                subdivision_arbre(arbre, e) 
                pour enfant dans arbre.enfants
                    insertion_etoile(enfant, arbre.e)
                pour enfant dans arbre.enfants
                    insertion_etoile(enfant, e)
                destruction(arbre.e)
        sinon
            maj_masse_cdm(arbre.sup_etoile, e)
            pour enfant dans arbre.enfants
                insertion_etoile(enfant, e)

Utilisation de l'arbre

• L'arbre est rempli: comment on calcule la force sur le corps 1?
• Parcours de l'arbre:
  • si la distance entre 1 et le centre de masse est suffisante, on utilise la masse totale et centre de masse pour calculer la force.
  • sinon, on continue le parcours

Calcul de la force

Calcul de la force sur 1

• Le cadrant ID ne contient que 1, rien à faire.

Calcul de la force

Calcul de la force sur 1

• Le cadrant SG ne contient 5 corps.

Calcul de la force

Calcul de la force sur 1

• La distance entre 1 et le centre de masse de SG est d.

Calcul de la force

Calcul de la force sur 1

• La distance entre 1 et le centre de masse de SG est d.
• Est-ce que d est assez grand?
• On va comparer avec la distance d avec la taille du quadrant s.

Critère

\theta

• On compare

  d=||\vec x_1-\vec x_{cm}||
  avec
  s
  la taille du quadrant.

• Le domain est assez éloigné si

  \frac{s}{d}<\theta,

• \theta
  est la valeur de seuil.

• Une valeur typique est

  \theta=0.5
  , donc la condition devient
  d>2s.

Calcul de la force

Calcul de la force sur 1

• Ici
  d<2s
  , domaine rejeté.
• ON descend dans l'arbre.

Calcul de la force

Calcul de la force sur 1

• s est plus petit, mais....
• Cela ne suffit pas
  d<2s
  , domaine rejeté.

Calcul de la force

Calcul de la force sur 1

• Les nœuds sont des feuilles, on calcule la force.
• On ajoute la force qu'ils exercent sur 1.

Algorithme pour le calcul de la force

Pour calculer la force sur un corps c, on parcourt l'arbre en commençant par la racine:

• Si le nœud n est une feuille et n'est pas c, on ajoute la force dûe à n sur c;
• Sinon si
  s/d<\theta
  , on traite n comme une feuille et on ajoute la force dûe à n sur c;
• Sinon on continue sur les enfants récursivement.

Continuons notre exemple précédent!

Calcul de la force

Calcul de la force sur 1

• Il y a deux corps dans le quadrant vert.
• Quel est le critère pour remplacer les étoiles par leur centre de masse?

. . .

• Et oui!
  d>2s
  on peut remplacer les étoiles par leur centre de masse!

Algorithme du calcul de force

Écrire le pseudo-code-code du calcul de la force

\footnotesize

rien maj_force_sur_etoile(arbre, e, theta)
    si est_vide(arbre)
        retourne

    si est_feuille(arbre) && contient_etoile(arbre) && dans_le_quadrant(arbre.q, e.x)
        maj_force(e, arbre.e)
    sinon si noeud_assez_loin(arbre, e, theta)
        maj_force(e, arbre.sup_etoile)
    sinon
        pour enfant dans enfants
            maj_force_sur_etoile(enfant, e, theta)

Les B-arbres

Problématique

• Grands jeux de données (en 1970).
• Stockage dans un arbre, mais l'arbre tiens pas en mémoire.
• Regrouper les sous-arbres en pages qui tiennent en mémoire.

Exemple

• 100 nœuds par page et l'arbre comporte
  10^6
  nœuds:
  • Recherche B-arbre:
    \log_{100}(10^6)=3
    ;
  • Recherche ABR:
    \log_2(10^6)=20
    .
• Si on doit lire depuis le disque:
  10\mathrm{ms}
  par recherche+lecture:
  • 30\mathrm{ms}
    (lecture beaucoup plus rapide que recherche) vs
    200\mathrm{ms}=0.2\mathrm{s}
    .

Remarques

• On sait pas ce que veut dire B: Bayer, Boeing, Balanced?
• Variante plus récente B+-arbres.

Les B-arbres

Illustration, arbre divisé en pages de 3 nœuds

. . .

Utilisation

• Bases de données (souvent très grandes donc sur le disque);
• Système de fichier.

Les B-arbres

Avantages

• Arbres moins profonds;
• Diminue les opération de rééquilibrage;
• Complexité toujours en
  \log(N)
  ;

. . .

Définition: B-arbre d'ordre

n

• Chaque page d'un arbre contient au plus
  2\cdot n
  clés;
• Chaque page (excepté la racine) contient au moins
  n
  clés;
• Chaque page qui contient
  m
  clés contient soit:
  • 0
    descendants;
  • m+1
    descendants.
• Toutes les pages terminales apparaissent au même niveau.

Les B-arbres

Est-ce un B-arbre?

. . .

Oui!

• Dans chaque nœud les clés sont triées.
• Chaque page contient au plus
  n
  nœuds: check;
• Chaque nœud avec
  m
  clés a
  m+1
  descendants;
• Toutes les feuilles apparaissent au même niveau.

Les B-arbres

Exemple de recherche: trouver 32

. . .

• Si n plus petit que la 1e clé ou plus grand que la dernière descendre.
• Sinon parcourir (par bissection ou séquentiellement) jusqu'à trouver ou descendre entre 2 éléments.

Les B-arbres

La recherche de la clé C algorithme

0. En partant de la racine.
1. Si on est dans une feuille:
   • Si la C est dans une page, retourner la page;
   • Sinon c'est perdu.
2. Sinon:
   • Tant que C > page passer à la page suivante
   • Descendre

Les B-arbres

Disclaimer

• Inspiration de https://en.wikipedia.org/wiki/B-tree

Exemples d'insertion: 1

. . .

• L'arbre est vide, on insère juste dans la première page.

Les B-arbres

Exemples d'insertion: 2

. . .

• La première page est pas pleine, on insère dans l'ordre (après 1).

Les B-arbres

Exemples d'insertion: 3

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 3

. . .

• La page est pleine, on crée deux enfants.
• On choisit, 2, la médiane de 1, 2, 3 et il est inséré à la racine.
• 1 descend à gauche, 3 descend à droite.

Les B-arbres

Exemples d'insertion: 4

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 4

. . .

• On pourrait insérer à droite de 2, mais... ça ferait 2 parents pour 2 enfants (mais m parents => m+1 enfants ou 0);
• On descend à droite (4 > 2);
• On insère à droite de 3.

Les B-arbres

Exemples d'insertion: 5

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 5

. . .

• On descend à droite (on peut pas insérer à la racine comme pour 4);
• On dépasse la capacité de l'enfant droite;
• 4, médiane de 3, 4, 5, remonte à la racine;
• On crée un nouveau nœud à droite de 4;
• La règle m => m+1 est ok.

Les B-arbres

Exemples d'insertion: 6

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 6

. . .

• 6 > 4 on descend à droite;
• 6 > 5 et on a à la place à droite, on insère.

Les B-arbres

Exemples d'insertion: 7

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 7

. . .

• 7 > 4 on descend à droite;
• 7 > 6 mais on a dépassé la capacité;
• 6 est la médiane de 5, 6, 7, remonte à la racine;
• 5 reste à gauche, 7 à droite, mais 6 fait dépasser la capacité de la racine;
• 4 est la médiane de 2, 4, 6, 4 remonte, 2 reste à gauche, 6 à droite.

Les B-arbres

L'algorithme d'insertion

0. Rechercher la feuille (la page a aucun enfant) où insérer;
1. Si la page n'est pas pleine insérer dans l'ordre croissant.
2. Si la page est pleine, on sépare la page en son milieu :
   1. On trouve la médiane, M, de la page;
   2. On met les éléments < M dans la page de gauche de M et les > M dans la page de droite de M;
   3. M est insérée récursivement dans la page parent.

Les B-arbres

Exercice: insérer 22, 45, 50 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice: insérer 5 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice: insérer 32, 55, 60 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice: insérer 41 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice (matrix, 15min)

• Insérer 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 2, 14, 28, 32, 41,
• Dans un B-arbre d'ordre 2.