Construction de monoïdes bigènes

1) Introduction

On représente le monoïde engendré par deux éléments `a,b`, par un graphe orienté où les sommets sont les éléments du monoïde. Chaque sommet possède deux arrètes partantes libéllées `a` et `b`. Le sommet racine est l'élément neutre du monoïde. Et pour chaque sommet `x`, l'arrête libéllée `a` partant de `x` arrive sur le sommet `x"*"a`, et l'arrête libéllée `b` partant de `x` arrive sur le sommet `x"*"b`, où `"*"` est la loi du monoïde.

On programme la construction du monoïde en Python.

2) Installation spécifique de python dans un dossier (environnement virtuel)

Créer un dossier Python1 et exécuter la commande : python -m venv Python1
Une foix créée. Pour activer l'environnement virtuel : source Python1/bin/activate
Pour desactiver l'environnement virtuel : deactivate
Pour installer le module python numpy dans l'environnement virtuel, activez-le et exécuter : python -m pip install numpy

Pour lister les modules installés : python -m pip list.
Pour lancer Python : python

Pour exécuter un script python a.py et ouvrir l'interpéteur qui l'a exécuté : python -i a.py

Pour exécuter un script python a.py dans l'interpéteur :

with open("a.py") as f:
        exec(f.read())

3) Structure

On utilise le module numpy qui permet de manipuler des tableaux de façon efficace. Le monoïde est mémorisé sous forme d'un graphe. C'est une immense liste de cellules, et chaque cellule contient 4 index et 16 flags. On choisit comme index des nombres entiers non-signés tenant sur 4 octets. La cellule occupe donc 18 octets.

On utilise ChatGPT pour faire la programmation :

Définit en python et en utilisant numpy, un tableau d'une dimension dont chaque cellule est une donnée structurée comme suit : {     'a' uint32     'b' uint32     'd' uint32     'L' uint32     'u0' bool     'u1' bool     'u2' bool     'u3' bool     'u4' bool     'u5' bool     'u6' bool     'u7' bool     'u8' bool     'u9' bool     'uA' bool     'uB' bool     'uC' bool     'uD' bool     'uE' bool     'uF' bool } Et le tableau doit occuper une taille mémoire minimale.

Pour définir en Python avec NumPy un tableau d'une dimension contenant des données structurées avec une taille mémoire minimale, on peut utiliser un dtype structuré (structured dtype) combinant des entiers uint32 et des booléens regroupés sous forme de bits dans un champ entier. Voici comment procéder : import numpy as np # Définir un dtype structuré compact dtype = np.dtype([ ('a', 'u4'), # uint32 ('b', 'u4'), # uint32 ('d', 'u4'), # uint32 ('L', 'u4'), # uint32 ('flags','u2') # uint16 pour contenir 16 bits booléens (u0 à uF) ]) # Créer un tableau de 10 éléments (par exemple) tableau = np.zeros(10, dtype=dtype) Gestion des booléens (u0 à uF) On regroupe les 16 booléens dans un champ uint16 nommé flags. Chaque bit représente un booléen : u0 est le bit 0 u1 est le bit 1 ... uF est le bit 15 Fonctions utilitaires Voici des fonctions pour manipuler les booléens individuellement : def set_flag(entry, index, value): if value: entry['flags'] |= (1 << index) else: entry['flags'] &= ~(1 << index) def get_flag(entry, index): return bool((entry['flags'] >> index) & 1) Exemple d'utilisation # Activer u3 (bit 3) sur la 1re cellule set_flag(tableau[0], 3, True) # Lire la valeur de u3 print("u3 =", get_flag(tableau[0], 3)) # True # Désactiver u3 set_flag(tableau[0], 3, False) # Lire la valeur de u3 après désactivation print("u3 =", get_flag(tableau[0], 3)) # False Mémoire utilisée Chaque entrée fait : 4 × 4 octets pour a, b, d, L = 16 octets 2 octets pour flags Total : 18 octets par élément (plus éventuellement 6 octets de padding selon l'alignement si align=True, mais ce n’est pas le cas ici). Cela correspond à une représentation mémoire très compacte pour ce type de données.

 

Dans l'exemple, le tableau 'tableau' peut-t-il s’agrandir en cours de route ?

Non, le tableau tableau créé avec NumPy ne peut pas s’agrandir dynamiquement une fois qu’il est initialisé. En effet : Les tableaux NumPy sont de taille fixe. Leur mémoire est allouée en bloc contigu, et leur dimension ne peut pas être étendue sans recréer un nouveau tableau. Que faire si tu veux l’agrandir ? Si tu veux un comportement de type « tableau dynamique », il y a deux options : 1. Recréation manuelle avec redimensionnement import numpy as np # Taille initiale tableau = np.zeros(10, dtype=dtype) # Pour l’agrandir : nouveau = np.zeros(20, dtype=dtype) # nouvelle taille nouveau[:10] = tableau # copie des données tableau = nouveau Cette méthode est typique des implémentations internes de tableaux dynamiques comme les listes Python ou les vecteurs C++. 2. Utiliser une liste Python en attendant Si tu veux ajouter progressivement des éléments, tu peux temporairement stocker les entrées dans une liste, puis convertir en tableau NumPy à la fin : liste_entries = [] # Ajouter des éléments dynamiquement liste_entries.append((1, 2, 3, 4, 0b0000000000001010)) # exemple # Puis conversion en NumPy array tableau = np.array(liste_entries, dtype=dtype) En résumé Non : les tableaux NumPy ne s’agrandissent pas automatiquement. Oui : tu peux simuler cela en recréant un tableau plus grand ou en utilisant une liste intermédiaire.

4) Gestion de la mémoire

Au cours de l'évolution du graphe, des cellules vont être utilisées puis libérées. Pour gérer efficacement l'allocation de cellules, on maintient l'ensemble des cellules libres en une chaine de cellules libres avec une première cellule vide d'indexe `L`. Chaque cellule libre possède un attribut `L` qui contient l'index d'une cellule libre suivante. Et la dernière cellule libre contient comme attribut `L` la valeur `sf"nada"` qui est la valeur maximal où tous les bits sont à 1, et qui représente le rien.

On demande à ChatGPT de programmer cela :

Crée un tableau `M` de 1000 000 000 cellules et initialise-le comme suit : Pour chaque cellule, l'attribut `L` contient l'indexe de la cellule suivante, et la dernière cellule contient comme attribut L la valeur maximal où tous les bits sont à 1.

Créer un tableau NumPy de 1 milliard de cellules structuré comme tu l’as défini (avec des uint32 et un champ flags) est faisable, mais très exigeant en mémoire RAM. Calcul mémoire avant de commencer Chaque cellule contient : a, b, d, L → 4 champs uint32 → 4 × 4 = 16 octets flags → 1 champ uint16 = 2 octets Total : 18 octets par cellule Pour 1 milliard (10⁹) de cellules : 18 octets × 1_000_000_000 = 18 Go de RAM Ce tableau nécessite au moins 18 Go de RAM. Vérifie que ton système peut le supporter avant d’exécuter ce code. Code pour créer et initialiser le tableau import numpy as np # Définition du dtype compact dtype = np.dtype([ ('a', 'u4'), ('b', 'u4'), ('d', 'u4'), ('L', 'u4'), ('flags', 'u2') ]) # Création du tableau (! RAM ~18 Go) N = 1_000_000_000 M = np.zeros(N, dtype=dtype) # Initialisation du champ 'L' M['L'][:-1] = np.arange(1, N, dtype='u4') # De 1 à N-1 M['L'][-1] = 0xFFFFFFFF # Dernière valeur : tous les bits à 1 pour uint32 Conseils importants Tu dois exécuter ce code sur une machine avec au moins 32 Go de RAM, idéalement plus. Si tu veux tester le comportement sans risque, commence par un échantillon plus petit : N = 10_000 # Pour tester Souhaites-tu aussi une version mappée en mémoire disque (memmap) pour éviter de tout charger en RAM ?

Oui

Parfait ! Utiliser un np.memmap permet de manipuler un tableau très large (comme ton milliard de cellules) sans saturer la RAM, car NumPy ne charge que les portions nécessaires en mémoire. Voici comment faire : Version avec np.memmap sur disque import numpy as np import os # Définition du dtype structuré compact dtype = np.dtype([ ('a', 'u4'), ('b', 'u4'), ('d', 'u4'), ('L', 'u4'), ('flags', 'u2') ]) # Nombre d'éléments N = 1_000_000_000 # 1 milliard # Nom du fichier disque (tu peux le déplacer ensuite si besoin) fichier = 'tableau_mmap.dat' # Création du fichier mémoire mappée M = np.memmap(fichier, dtype=dtype, mode='w+', shape=(N,)) # Initialisation du champ 'L' M['L'][:-1] = np.arange(1, N, dtype='u4') # de 1 à N-1 M['L'][-1] = 0xFFFFFFFF # dernier = tous les bits à 1 # Flush pour forcer l'écriture sur disque M.flush() À savoir mode='w+' : création ou écrasement du fichier existant. M.flush() : très important pour forcer l’écriture physique sur disque. Accès ultérieur : # Réouvrir plus tard sans recharger tout M = np.memmap('tableau_mmap.dat', dtype=dtype, mode='r+', shape=(1_000_000_000,))