Les listes chainées

 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 chaque élément de base.

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 = []
    

Les variables de classes (lettre, chiffre, possible) vont servir à générer des données aléatoires pour l'identifiant d'un nouveau maillon et pour sa valeur.

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 point le plus délicat est la recherche du dernier bloc. On ne peut pas systématiquement dépiler le dernier maillon, seul le chainage contient l'ordre des maillons. Le dernier maillon est le seul dont l'identifiant n'est pas référencé par un autre bloc.

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)
        
    

L'identifiant de la sentinelle sera spécial pour ne pas être confondu avec un maillon normal. 

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.