User

I. Introduction

Dans 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 [x₀, x_n-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 - Visualiser dans une fen�tre � part

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 - Visualiser dans une fen�tre � part

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 - Visualiser dans une fen�tre � part

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 :

1. liste_elements: liste d'�l�ments dans laquelle on effectue la recherche ;
2. nom_cle: nom de la cl� associ�e � la valeur recherch�e (ex.: "num_commande") ;
3. valeur_cle: valeur de cl� recherch�e (ex.: 10) ;
4. cdf: fonction de r�partition de param�tres loc et scale (distribution uniforme : stats.uniform.cdf(x, loc, scale), etc.) ;
5. loc: param�tre de position de la distribution (ex. : moyenne pour la distribution de Gauss) ;
6. 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 - Visualiser dans une fen�tre � part

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 - Visualiser dans une fen�tre � part

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 - Visualiser dans une fen�tre � part

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