mardi 12 octobre 2021

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.

samedi 18 septembre 2021

Algorithmie: comment trouver la 2eme valeur la plus élevée d'une liste

 Lors des entretiens d'embauche d'un développeur, il est possible de rencontrer cette question: 

 Comment  trouver le la 2eme valeur la plus élevée d'une liste ? .

Bien qu'anodine, cette question ouvre vers de nombreuses déclinaisons et soulève des nouvelles questions.

Est ce que la liste est finie ?, de taille compatible avec la mémoire du serveur ? etc..

Première réponse qui vient spontanément: trier la liste et prendre le 2eme élément.

Démonstration en Python

Commençons par générer une liste aléatoire de 1000000 éléments de 1 à 50.

 
import random
randomlist = []
for i in range(0,1000000):
    n = random.randint(1,50)
    randomlist.append(n)

Puis récupérons le deuxième élément après le tri.

 
%%time
listetriee = sorted(randomlist,reverse =1)
print(listetriee[1])

50
Wall time: 210 ms

Erreur, on devrait retourner vraisemblablement la valeur 49 et non pas 50.

En examinant le début de la liste triée:

print(listetriee[:20])

[50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50]

On n'a pas traité le cas des valeurs identiques... Pour rendre unique les éléments d'une liste, le plus simple est de passer par un 'set'.

 
%%time
unique = set(randomlist)
print('taille de la liste:', len(unique))
listetriee =sorted(unique, reverse = 1)
print(listetriee[1])

taille de la liste: 50
49
Wall time: 48 ms

La taille finale de la liste fait 50 (ce qui est normal) Le temps d exécution est plus petit en raison de cette diminution de la taille. Le résultat est à présent correct.

Cette méthode ne fonctionnerait pas avec une liste issue d'un flux où d'un fichier de plusieurs Go. Elle ne pourrait pas tenir en mémoire centrale.
Il faut dissocier la recherche des deux éléments les plus élevés et l'alimentation au fils de l'eau.

Pour la recherche du 2eme élément, le tri de toute la collection est inutile: on ne désire que le premier et le deuxième élément. La connaissance du premier élément ne sert qu'à ordonner le deuxième (celui qui vient juste après le premier).

%%time
unmax = 0
deuxmax = 0
for i in randomlist:
    if i > unmax:
        deuxmax = unmax
        unmax = i
    else:
        if i > deuxmax and i < unmax:
            deuxmax =i
            
print(deuxmax)        

49
Wall time: 73.5 ms

Ici, on va parcourir la liste sans la trier, juste sélectionner les deux plus fortes valeurs.
Le temps d'exécution donnée par %%time dans jupyter est plus important que le tri sur la liste sans doublon mais plus rapide que le tri complet de la liste.

A présent on peut s'attaquer au problème de l'alimentation à la volée de ce filtre, à partir par exemple de la lecture d'un fichier.

Nous allons tout d abord fabriquer un fichier de nombre à partir d'une compréhension de liste.

maliste = [ random.randint(1,50) for i in range(10000000)]
with open('grosfichier.txt', 'a') as the_file:
    for i in maliste:
        the_file.write(f"{i}\n")
        

Puis on va lire le fichier et le filtrer à la volée.

%%time
unmax = 0
deuxmax = 0
with open('grosfichier.txt', 'r')  as file:
    for ligne in file:
        i = int(ligne[:-1])
        if i > unmax:
            deuxmax = unmax
            unmax = i
    else:
        if i > deuxmax and i < unmax:
            deuxmax =i
print(deuxmax)


49
Wall time: 3.65 s
        

Et voila, traitement sera plus long du fait de la lecture du fichier mais le filtre sera capable de traiter plusieurs giga de données sans risque de saturer la mémoire.


Good hacking ! with http://hilite.me/ pour la mise en forme du code

dimanche 8 août 2021

Guide de survie pour pandas et Numpy

 

Les librairies Pandas et Numpy sont deux piliers de l’outillage Python pour l’apprentissage automatique. Aussi faut-il connaitre quelques subtilités pour éviter de perdre du temps à la recherche d’erreur.

 Par expérience, je réserve l’utilisation de Pandas au chargement des données et à leur transformation pour ensuite les exporter vers les frameworks comme Tensorflow ou Pytorch.

La phase d’export d’une colonne vers un array Numpy doit s’accompagner d’une vérification des dimensions de l’export. Car Pandas l’exporte vers un tableau qui est à plutôt les caractéristiques d’une liste.

Exemple : Création d'un dataFrame et export vers Numpy d'une colonne.

 


Une dimension unique comme (3,) est le propre d’une série au sens Dataframe ou d’un type liste en Python : ce n’est pas une vrai matrice (array) Numpy.

Dans numpy on peut repérer 3 structures particulières :

Les listes

La matrice sur 1 seule ligne mais bien de dimension 2

La matrice d’une colonne mais bien de dimension 2 (un vecteur)

Il est possible de passer d’une structure à une autre par une opération de ‘reshape’

 Illustration ci-dessous:


Une structure a 1 dimension peut provoquer des erreurs dans des fonctions d'apprentissage automatique et surtout être la cause d'erreur de broadcasting.

Le broadcasting dans numpy.

C'est un mécanisme puissant mais qui peut provoquer des erreurs en cascade.

Les opérations  entre matrice imposent de respecter des contraintes sur les dimensions des matrices:
Le broadcasting permet des opérations hybrides à mi chemin entre les opérations  entre des matrices ou des opérations avec des scalaires.

Exemple : création de 3 matrices: une de 3X3 , une de 1X3 et enfin une de 3X1:


Si on réalise la multiplication scalaire de la matrice a par le 'scalaire' 2 on obtiendra: 

Que ce passe-t-il si je souhaite multiplier la matrice a (3X3) par b (1X3) ? Comme on pourrait le faire avec un scalaire ?  Cette opération hybride n'est pas autorisée et c'est là qu'intervient le broadcasting. Numpy va étendre sous certaines conditions les matrices. 
Les conditions sont les suivantes:
  • Dimensions identiques
  • Une des deux dimensions est égale à 1 
 
Numpy va prendre la ligne de la matrice b et la dupliquer vers le bas afin d'avoir une matrice 3X3.

 


Erreurs de broadcasting.

Prenons maintenant un cas qui va générer des erreurs en cascade.

Soit deux matrice de dimension 5X1 

Leur multiplication 'scalaire' va donner une matrice 5X1


 Si on prend la matrice 'c' qui n'a qu'une seule dimension: le résultat sera différent : une matrice de 5X5




Ainsi la règle d'or est de toujours vérifier la forme de la matrice (shape) avant une opération.