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