Mathématiques et Python : déterminer la position de valeurs dans une liste triée en fonction de leur répartition,

Un billet blog de Denis Hulo

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 :

642309

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 :

642262

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 :

642256

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].

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 :

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 return 0
else: # sinon
if x < (loc+scale): # si x 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.

642262

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)

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 :