I. IntroductionDans une liste ordonnée de valeurs, si on a une idée de leur répartition (distribution uniforme, de Gauss, etc.) et si on connaît leur nombre total, alors, on peut estimer la position d'une valeur quelconque dans la liste.
On souhaite dans notre cas créer une fonction Python qui puisse déterminer la position d'un élément dans une liste en utilisant ce principe.
On proposera également à la fin un exemple de mise en œuvre avec la recherche d'une commande dans une liste ordonnée à partir de son numéro de référence.
II. Principe de la recherche
Prenons pour simplifier une liste de n valeurs qui se répartissent suivant une distribution de probabilité ayant comme paramètre de position loc, représentant généralement la moyenne des valeurs, et comme paramètre de dispersion scale, correspondant le plus souvent à l'écart-type :
Alors la valeur de la fonction de répartition en x, notée F(x), ayant comme paramètres loc et scale, donne une estimation de la proportion de valeurs inférieures ou égales à x :
Cette estimation fournit donc aussi une indication sur la position de x dans la liste.
Si on considère maintenant l'intervalle contenant les n valeurs [x0, xn-1], auquel on peut faire correspondre l'intervalle contenant les n indices [0, n-1] de la liste Python.
La position approximative de x dans la liste, c'est à dire sur l'intervalle [0, n-1] de longueur n-1 est donné par la formule :
indice_x= F(x)*(n-1)
Comme on souhaite avoir une valeur entière, on va arrondir le résultat à l'entier le plus proche :
indice_x = round(F(x)*(n-1))
Ensuite, on effectuera un parcours séquentiel à partir de cette valeur d'indice jusqu'à l'élément recherché.
Dans la pratique, on peut imaginer une liste de commandes classées suivant leur numéro. Si on connaît la fonction de répartition des numéros de commande (loi uniforme, etc.), on peut alors en déduire leur rang ou leur position dans la liste.
III. Distributions en Python
La librairie SciPy contient un grand nombre de distributions de probabilités (distribution uniforme, de Gauss, etc.), mais on peut aussi bien sûr créer sa propre fonction de répartition.
III-A. Loi uniforme
Un objet uniform du module SciPy est utilisé pour une variable aléatoire continue suivant une loi uniforme :
Dans sa forme standard, la distribution est uniforme sur [0, 1]. En utilisant les paramètres loc=a et scale=b-a, on obtient une distribution uniforme sur [loc, loc + scale].
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 | from scipy import stats # fonction de répartition de la loi uniforme continue sur l'intervalle [0, 1] p1 = stats.uniform.cdf(0.5) # Fonction de répartition cdf - calcul de P(X ≤ 0.5) = 0.5 # fonction de répartition de la loi uniforme sur l'intervalle [1, 10] p2 = stats.uniform.cdf(x=5, loc=1,scale=10-1) # Fonction de répartition cdf - calcul de P(X ≤ 5) |
Si vous ne souhaitez pas utiliser de librairie, alors le code de la fonction de répartition de la loi uniforme devrait ressembler à cela :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 | def uniform_cdf(x,loc,scale): # fonction de répartition de la loi uniforme de paramètres loc=a et scale=(b-a) : F(x) = (x-a)/(b-a) pour a≤x≤b if x<loc: # si x<a return 0 else: # sinon if x < (loc+scale): # si x<b return (x-loc)/scale else: # sinon return 1 |
III-B. Loi normale
Un objet norm est utilisé pour une variable aléatoire continue suivant une loi normale.
Le paramètre loc désigne la moyenne et l'argument scale l'écart type.
La fonction de répartition de la loi normale centrée réduite en x est appelée ainsi :
p1 = stats.norm.cdf(x)
La fonction de répartition de la loi normale pour une variable aléatoire de moyenne m et d'écart type s :
p2 = stats.norm.cdf(x, loc=m, scale=s)
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 | from scipy import stats # fonction de répartition en x=0.2 de la loi normale centrée et réduite N(0,1) p1 = stats.norm.cdf(0.2) # calcul de la probabilité P(X ≤ 0.2) # fonction de répartition en x=3.5 de la loi normale N(2.5, 4) p2 = stats.norm.cdf(3.5, loc=2.5, scale=4) # calcul de la probabilité P(X ≤ 3.5) |
IV. Implémentation en Python
On présente maintenant la fonction Python qui permet de déterminer la position d'un élément dans une liste en utilisant le principe décrit précédemment. Puis, on propose un exemple de mise en œuvre avec la recherche d'une commande dans une liste ordonnée à partir de son numéro de référence.
IV-A. Fonctions de recherche d'un élément
Elle permet de rechercher un élément dans une liste de dictionnaires à partir d'une valeur de clé et de la fonction de répartition des valeurs associées à cette clé.
Arguments de la fonction rechercher_element :
- liste_elements: liste d'éléments dans laquelle on effectue la recherche ;
- nom_cle: nom de la clé associée à la valeur recherchée (ex.: "num_commande") ;
- valeur_cle: valeur de clé recherchée (ex.: 10) ;
- cdf: fonction de répartition de paramètres loc et scale (distribution uniforme : stats.uniform.cdf(x, loc, scale), etc.) ;
- loc: paramètre de position de la distribution (ex. : moyenne pour la distribution de Gauss) ;
- scale: paramètre de dispersion de la distribution (ex. : écart-type pour la distribution de Gauss).
Elle prend donc comme argument une fonction de répartition comme celles disponibles dans le module scipy.stats (stats.uniform.cdf(x, loc, scale), etc.) :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def rechercher_element(liste_elements, nom_cle, valeur_cle, cdf, loc, scale): # nombre d'éléments de la liste n = len(liste_elements) # estimation de la position de la valeur de clé en fonction de la répartition des valeurs indice_est = round(cdf(x=valeur_cle,loc=loc,scale=scale)*(n-1)) indice_val = indice_est # tant que la valeur de position indice_val est inférieure à la valeur de clé recherchée while liste_elements[indice_val][nom_cle]<valeur_cle: indice_val+=1 # on incrémente l'indice # tant que la valeur de position indice_val est supérieure à la valeur de clé recherchée while liste_elements[indice_val][nom_cle]>valeur_cle: indice_val-=1 # on décrémente l'indice # si la valeur a été trouvée if liste_elements[indice_val][nom_cle]==valeur_cle: # affiche l'écart entre la position réelle de la valeur recherchée et sa position estimée print("Écart entre la position réelle et la position estimée : {0}\n".format(abs(indice_val-indice_est))) # renvoie l'élément recherché accompagné de sa position dans la liste return {'position': indice_val, 'élément': liste_elements[indice_val]} |
Note : En Python, un dictionnaire est un ensemble de paires clé: valeur, les clés devant être uniques au sein du dictionnaire.
IV-B. Test de la fonction de recherche
On dispose d'une liste de commandes (sans leur détail) ordonnées suivant leur numéro auto-incrémenté. Sachant qu'il peut y avoir quelques trous dans la numérotation de ces commandes dus à certaines suppressions, on admettra que ces identifiants se répartissent de façon approximativement uniforme dans la liste.
On souhaite dans cette situation retrouver la position d'une commande à partir de son identifiant :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | # liste des commandes clients liste_commandes = [{'num_commande': 1, 'date_commande': '12/02/2023', 'nom_client': 'Bonnaventure Sébastien', 'montant': 125.70}, {'num_commande': 2, 'date_commande': '14/02/2023', 'nom_client': 'Amat Laurent', 'montant': 223.55}, {'num_commande': 4, 'date_commande': '15/02/2023', 'nom_client': 'Le Breton Tiphaine', 'montant': 326.20}, {'num_commande': 5, 'date_commande': '17/02/2023', 'nom_client': 'Cardin Anthony', 'montant': 141.45}, {'num_commande': 6, 'date_commande': '17/02/2023', 'nom_client': 'Soudain Cyril', 'montant': 544.40}, {'num_commande': 8, 'date_commande': '18/02/2023', 'nom_client': 'Valdes Lucien', 'montant': 342.25}, {'num_commande': 9, 'date_commande': '18/02/2023', 'nom_client': 'Harry John', 'montant': 347.25}, {'num_commande': 10, 'date_commande': '18/02/2023', 'nom_client': 'Thiel Xavier', 'montant': 316.25}, {'num_commande': 11, 'date_commande': '19/02/2023', 'nom_client': 'Gillet Mélanie', 'montant': 716.30}, {'num_commande': 13, 'date_commande': '20/02/2023', 'nom_client': 'Richard Océane', 'montant': 613.20}, {'num_commande': 14, 'date_commande': '20/02/2023', 'nom_client': 'Dias Pauline', 'montant': 113.20}, {'num_commande': 15, 'date_commande': '21/02/2023', 'nom_client': 'Moulin Olivier', 'montant': 512.50}] # premier et dernier élément de la liste : bornes de l'intervalle [a, b] de la loi uniforme a = liste_commandes[0]['num_commande']; b = liste_commandes[-1]['num_commande'] # recherche de la commande à partir de son numéro et de la fonction de répartition de la loi uniforme commande = rechercher_element(liste_commandes, 'num_commande', 10, stats.uniform.cdf, loc=a, scale=b-a) if commande: # si la commande a été trouvée # affiche la commande trouvée et sa position dans la liste print("Commande trouvée :") print(commande) else: # sinon print("Le numéro de commande n'a pas été trouvé !") |
Le code affiche :
Écart entre la position réelle et la position estimée : 0
Commande trouvée :
{'position': 7, 'élément': {'num_commande': 10, 'date_commande': '18/02/2023', 'nom_client': 'Thiel Xavier', 'montant': 316.25}}
On constate que l'écart entre la position réelle de la commande recherchée et son indice évalué à l'aide de la fonction de répartition vaut 0. Par conséquent, on accède directement à l'élément recherché en utilisant notre formule de calcul de position.
V. Module complet
On donne pour finir le code du module pour effectuer les tests :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | from scipy import stats # librairie contenant les distributions de probabilité def uniform_cdf(x,loc,scale): # fonction de répartition de la loi uniforme de paramètres loc=a et scale=(b-a) : F(x) = (x-a)/(b-a) pour a≤x≤b if x<loc: # si x<a return 0 else: # sinon if x < (loc+scale): # si x<b return (x-loc)/scale else: # sinon return 1 def rechercher_element(liste_elements, nom_cle, valeur_cle, cdf, loc, scale): try: # nombre d'éléments de la liste n = len(liste_elements) # estimation de la position de la valeur de clé en fonction de la répartition des valeurs indice_est = round(cdf(x=valeur_cle,loc=loc,scale=scale)*(n-1)) indice_val = indice_est # tant que la valeur de position indice_val est inférieure à la valeur de clé recherchée while liste_elements[indice_val][nom_cle]<valeur_cle: indice_val+=1 # on incrémente l'indice # tant que la valeur de position indice_val est supérieure à la valeur de clé recherchée while liste_elements[indice_val][nom_cle]>valeur_cle: indice_val-=1 # on décrémente l'indice # si la valeur a été trouvée if liste_elements[indice_val][nom_cle]==valeur_cle: # affiche l'écart entre la position réelle de la valeur recherchée et sa position estimée print("Écart entre la position réelle et la position estimée : {0}\n".format(abs(indice_val-indice_est))) # renvoie l'élément recherché accompagné de sa position dans la liste return {'position': indice_val, 'élément': liste_elements[indice_val]} # gestion d'erreur except IndexError: # si l'indice est en dehors des limites return None # on renvoie None : élément non trouvé # recherche d'une commande dans une liste : répartition uniforme des numéros de commandes print("========================================================================================") print(" Recherche d'une commande dans une liste : répartition uniforme des numéros de commande ") print("========================================================================================\n") # liste des commandes clients liste_commandes = [{'num_commande': 1, 'date_commande': '12/02/2023', 'nom_client': 'Bonnaventure Sébastien', 'montant': 125.70}, {'num_commande': 2, 'date_commande': '14/02/2023', 'nom_client': 'Amat Laurent', 'montant': 223.55}, {'num_commande': 4, 'date_commande': '15/02/2023', 'nom_client': 'Le Breton Tiphaine', 'montant': 326.20}, {'num_commande': 5, 'date_commande': '17/02/2023', 'nom_client': 'Cardin Anthony', 'montant': 141.45}, {'num_commande': 6, 'date_commande': '17/02/2023', 'nom_client': 'Soudain Cyril', 'montant': 544.40}, {'num_commande': 8, 'date_commande': '18/02/2023', 'nom_client': 'Valdes Lucien', 'montant': 342.25}, {'num_commande': 9, 'date_commande': '18/02/2023', 'nom_client': 'Harry John', 'montant': 347.25}, {'num_commande': 10, 'date_commande': '18/02/2023', 'nom_client': 'Thiel Xavier', 'montant': 316.25}, {'num_commande': 11, 'date_commande': '19/02/2023', 'nom_client': 'Gillet Mélanie', 'montant': 716.30}, {'num_commande': 13, 'date_commande': '20/02/2023', 'nom_client': 'Richard Océane', 'montant': 613.20}, {'num_commande': 14, 'date_commande': '20/02/2023', 'nom_client': 'Dias Pauline', 'montant': 113.20}, {'num_commande': 15, 'date_commande': '21/02/2023', 'nom_client': 'Moulin Olivier', 'montant': 512.50}] # premier et dernier élément de la liste : bornes de l'intervalle [a, b] de la loi uniforme a = liste_commandes[0]['num_commande']; b = liste_commandes[-1]['num_commande'] # recherche de la commande à partir de son numéro et de la fonction de répartition de la loi uniforme commande = rechercher_element(liste_commandes, 'num_commande', 10, uniform_cdf, loc=a, scale=b-a) if commande: # si la commande a été trouvée # affiche la commande trouvée et sa position dans la liste print("Commande trouvée :") print(commande) else: # sinon print("Le numéro de commande n'a pas été trouvé !") |
VI. Conclusion
Comme on l'a vu, si on a une idée de la répartition des valeurs dans la liste ordonnée, et si on connait la taille de la liste, on peut accéder plus rapidement à l'élément recherché en utilisant la fonction de répartition des valeurs.
L'important est donc d'identifier la distribution de probabilité qui correspond le mieux à cette répartition avec les bons paramètres de position et de dispersion.
Sources :
https://fr.wikipedia.org/wiki/Loi_de_probabilit%C3%A9
https://fr.wikipedia.org/wiki/Foncti...C3%A9partition
https://fr.wikipedia.org/wiki/Loi_uniforme_continue
https://fr.wikipedia.org/wiki/Loi_normale
https://docs.scipy.org/doc/scipy/reference/stats.html