La connaissance des structures de bases en algorithmie est nécessaire pour bien maitriser la programmation.
Les listes chainées sont très utilisées dans les blockchains. Je vais présenter des exemples de manipulation de liste chainées en relation avec un des mécanismes qu'on trouve dans une blockain.
Principes d'une liste chainée.
Une liste chainée, est un ensemble d'élément (maillon) qui en plus de de porter une valeur, possède un attribut qui pointe vers l'élément suivant ou précédent. Une liste est doublement chainée si elle permet de se déplacer vers l'élément suivant (chainage avant) et précédent (chainage arrière).
Dans la cas d'une blockchain le chainage est vers l'arrière. Le bloc 'n' fourni les informations pour retrouver le bloc précédent (n-1). La raison est simple: dans le cas contraire : en cas d'ajout d'un bloc, il faudrait 'défaire' le dernier bloc pour mettre à jour son pointeur vers le bloc suivant.
Notre liste chainée.
Nous allons commencer par une liste à chainage arrière comme ceci:
(illustration réalisée avec https://excalidraw.com/)
En Python cela donnera:
class Maillon(): def __init__(self, idblock,valeur): self.idblock = idblock self.valeur= valeur self.prec = None
Pour la chaine en elle même :
import random import string class Blockchain: lettre = set(string.ascii_uppercase) lettre = lettre - {'I','O', 'Z'} chiffre = set([x for x in range(1,10)]) possible = lettre | chiffre def __init__(self): self.chaine = []
Ces données sont mis en œuvre dans une méthode de classe et une méthode statique (décorateurs). La difference n'est pas épaisse: la méthode de classe reçoit le nom de la classe en premier paramètre, et elle pourra ainsi accéder à des attributs de la classe. L'attribut 'possible' est la réunion d'une suite de chiffre et de lettre.
@classmethod def genere_id(cls): indexblock = [ random.choices(list(cls.possible))[0] for x in range(1,10)] return ''.join(str(x) for x in indexblock) @staticmethod def genere_montant(): return round(random.uniform(20.00, 2000.00), 2)
La creation d'une chaine et d'un premier maillon se fera de la manière suivante:
ma_chaine = Blockchain() un_maillon= Maillon(Blockchain.genere_id(), Blockchain.genere_montant()) ma_chaine.ajoute(un_maillon)
Un fois le maillon crée , il sera ajouté à la chaine par la méthode 'ajoute':
Cette méthode fait deux choses:
- Recherche du dernier maillon
- Ajout du maillon avec la référence sur le maillon précédent complétée.
def ajoute(self, maillon): maillon.prec = self.recherche_tete() self.chaine.append(maillon)
Le motif de recherche du dernier bloc va consister à avoir une boucle principale pour parcourir tous les blocs et pour chaque bloc rechercher son référencement par un bloc: deuxième parcours de la chaine.
def recherche_tete(self): cle = None for item in self.chaine: for item2 in self.chaine: if item.idblock == item2.idblock: continue if item2.prec == item.idblock: break else: return item.idblock
Cette méthode 'brute' a un gros inconvénient: le temps de traitement augmente exponentiellement en fonction du nombre de maillon : l'ajout d'un 2001eme maillon prendra plus de 3 minutes.
import matplotlib.pyplot as plt # Data for plotting t = [0, 500, 1000, 1500, 2000 ] s = [0.0 , 2.91 , 22.8 , 79.00, 191.00] fig, ax = plt.subplots() ax.plot(t, s) ax.set(xlabel='nombre de maillon', ylabel='duree', title='visualisation') ax.grid() plt.show()lock
La solution à ce problème de performance consistera à utiliser une 'sentinelle'.
Une sentinelle est un maillon spécial, crée à l'initialisation de la chaine et qui contiendra l'adresse du dernier bloc.
def ajoute_sentinelle(self): return Maillon('0'* 10, None) def ajoute(self, maillon,sentinelle= None): if sentinelle: _tmp_maillon =self.recherche_la_sentinelle() maillon.prec = _tmp_maillon.prec _tmp_maillon.prec = maillon.idblock else: maillon.prec = self.recherche_tete() self.chaine.append(maillon)
La recherche de la tête de la liste se résumera à rechercher la sentinelle. cette sentinelle ne fait pas partie d'une blockchain car on doit pouvoir la modifier à chaque ajout d'un nouveau bloc.