Trouver la valeur la plus proche dans une liste

"RENAUD Eric" <erenaud(retirerceci)@fr.fm> a écrit dans le message de
news:OowFQogFGHA.1032@TK2MSFTNGP11.phx.gbl...

Bonjour,

Comment dans une distribution trouver la valeur si elle n'est pas

identique,

celle qui est la plus proche (type INDEX sous excel).

Soit ma distribution :

100, 105, 110, 115, 120, ....

Si je tape 108, la valeur de référence doit être 105
Si je tape 116, la valeur de référence doit être 115

etc ...
Existe t'il une astuce ?

Hello,

Une astuce, à proprement parler, pas vraiment.
Quelques pistes:
- si tes données sont triées, une simple recherche
dichotomique
- si tes données sont dans un ordre quelcqonque, alors
un parcours complet s'impose.

Dans les 2 cas, rien de bien méchant.

Note; si tu tapes 108, la valeur de référence sera 110, car
108 est plus proche de 110 (abs(delta)=2) que de 105 (abs(delta)=3).

A moins que tu ne précises que tu cherches toujours la valeur la
plus proche, mais "en dessous" (toujours inférieure ou égale).

--
Jean-marc
Tester mon serveur (VB6) => http://myjmnhome.dyndns.org
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr

Tu mets un valeur extreme à une variable long ' Dif'

Dim DifMin as long

DiffMin = 62300

Tu peux par exemple, parcourrir ton tableau de valeur
Tue calcules la différence entre ta valeur de référence et celle du tableau
; si cette différence est < à DifMin alors
- tu gardes dans une variable l'indice du tableau
- tu mets ta différence inférieure dan ta variable DifMin

etc..
à la fin du tableau tu auras deux variables :
- difMin qui contiendra ta différence minimum
- une variable contenant l'indice du tableau => valeur ayant l'écart
minimum


Exemple : pour un tableau 'simple' ayant N valeurs

Dim Tableau(N) as long
Dim DifMin as long
Dim IndiceMin as long
Dim I as long
Const ValRef = 105 ' choix de la valeur dont on recherche le plus proche

DifMine000 ' si l'écart ne peut pas être supérieur à cette valeur ou alors
prendre une autre
For i= 0 to N
if Abs(tableau(I) - valref) <DifMin then
indicemin=I
difmin = abs(tableau(i)-valref)
end if
next

' maintnant
l'écart mùinimum est dans DifMin
et l'indice est IndiceMin

Driss

"Driss HANIB" <dhanib@club-internet.fr> a écrit dans le message de
news:%23wtZcIpFGHA.1028@TK2MSFTNGP11.phx.gbl...

Tu mets un valeur extreme à une variable long ' Dif'

Dim DifMin as long

DiffMin = 62300

Tu peux par exemple, parcourrir ton tableau de valeur
Tue calcules la différence entre ta valeur de référence et celle du

tableau

; si cette différence est < à DifMin alors
- tu gardes dans une variable l'indice du tableau
- tu mets ta différence inférieure dan ta variable DifMin

etc..
à la fin du tableau tu auras deux variables :
- difMin qui contiendra ta différence minimum
- une variable contenant l'indice du tableau => valeur ayant l'écart
minimum


Exemple : pour un tableau 'simple' ayant N valeurs

Dim Tableau(N) as long
Dim DifMin as long
Dim IndiceMin as long
Dim I as long
Const ValRef = 105 ' choix de la valeur dont on recherche le plus

proche

DifMine000 ' si l'écart ne peut pas être supérieur à cette valeur ou

alors

prendre une autre
For i= 0 to N
if Abs(tableau(I) - valref) <DifMin then
indicemin=I
difmin = abs(tableau(i)-valref)
end if
next

Hello Driss et les autres,

une petite remarque: dans tous les cas, tu calcules
la valeur absolue de tableau(i) - valref. C'est bien,
mais alors pourquoi la recalculer dans la boucle au
moment ou tu en as besoin?
Il vaut mieux le calculer dans une variable et s'éviter
ainsi un double calcul.
Le code devient quelque chose comme cela:

Function ChercheProche1(t() As Long, _
ByVal bInf As Long, _
ByVal bSup As Long, _
ByVal ValeurCible As Long, _
ByRef ValeurTrouve As Long, _
ByRef rang As Long) As Boolean
Dim DifMin As Long
Dim IndiceMin As Long
Dim i As Long
Dim curDif As Long

DifMin = 65000

For i = bInf To bSup
' un seul calcul
curDif = Abs(t(i) - ValeurCible)
If curDif < DifMin Then
rang = i
DifMin = curDif ' on reutilise sans recalcul
End If
Next i
ValeurTrouve = t(rang)
ChercheProche1 = True
End Function

J'ai aussi ajouté l'indice de boucle (i) dans le Next, c'est
plus lisible.

J'ai benchmarké par curiosité, en prenant le pire des cas c'est
à dire le cas ou les valeurs sont croissantes et la valeur
cherchée proche de la fin du tableau;

Le code avec la variable supplémentaire est 62% plus rapide, ce
qui est toujours bon à prendre :-)

Protocole:
- Tests fait avec 30 fois 1000 appels dans un tableau
de 10000 éléments, et 3 séries de mesures moyennées.
- Mesures du temps par GetTickCount()
- Temps de boucles mesurés négligeables

Code original: 260 ms (moyenne pour 1000 appels)
Code modifié : 162 ms (moyenne idem )

Ecart type de l'ordre de 8 ms (= +/-la précision GetTickCount)

--
Jean-marc
Tester mon serveur (VB6) => http://myjmnhome.dyndns.org
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr

Ok merci Jean-Marc

Driss

"Jean-Marc" <NO_SPAM_jean_marc_n2@yahoo.fr> a écrit dans le message de
news:43c5715a$0$13567$ba620e4c@news.skynet.be...

"Driss HANIB" <dhanib@club-internet.fr> a écrit dans le message de
news:%23wtZcIpFGHA.1028@TK2MSFTNGP11.phx.gbl...
> Tu mets un valeur extreme à une variable long ' Dif'
>
> Dim DifMin as long
>
> DiffMin = 62300
>
> Tu peux par exemple, parcourrir ton tableau de valeur
> Tue calcules la différence entre ta valeur de référence et celle du
tableau
> ; si cette différence est < à DifMin alors
> - tu gardes dans une variable l'indice du tableau
> - tu mets ta différence inférieure dan ta variable DifMin
>
> etc..
> à la fin du tableau tu auras deux variables :
> - difMin qui contiendra ta différence minimum
> - une variable contenant l'indice du tableau => valeur ayant l'écart
> minimum
>
>
> Exemple : pour un tableau 'simple' ayant N valeurs
>
> Dim Tableau(N) as long
> Dim DifMin as long
> Dim IndiceMin as long
> Dim I as long
> Const ValRef = 105 ' choix de la valeur dont on recherche le plus
proche
>
> DifMine000 ' si l'écart ne peut pas être supérieur à cette valeur ou
alors
> prendre une autre
> For i= 0 to N
> if Abs(tableau(I) - valref) <DifMin then
> indicemin=I
> difmin = abs(tableau(i)-valref)
> end if
> next



Hello Driss et les autres,

une petite remarque: dans tous les cas, tu calcules
la valeur absolue de tableau(i) - valref. C'est bien,
mais alors pourquoi la recalculer dans la boucle au
moment ou tu en as besoin?
Il vaut mieux le calculer dans une variable et s'éviter
ainsi un double calcul.
Le code devient quelque chose comme cela:

Function ChercheProche1(t() As Long, _
ByVal bInf As Long, _
ByVal bSup As Long, _
ByVal ValeurCible As Long, _
ByRef ValeurTrouve As Long, _
ByRef rang As Long) As Boolean
Dim DifMin As Long
Dim IndiceMin As Long
Dim i As Long
Dim curDif As Long

DifMin = 65000

For i = bInf To bSup
' un seul calcul
curDif = Abs(t(i) - ValeurCible)
If curDif < DifMin Then
rang = i
DifMin = curDif ' on reutilise sans recalcul
End If
Next i
ValeurTrouve = t(rang)
ChercheProche1 = True
End Function

J'ai aussi ajouté l'indice de boucle (i) dans le Next, c'est
plus lisible.

J'ai benchmarké par curiosité, en prenant le pire des cas c'est
à dire le cas ou les valeurs sont croissantes et la valeur
cherchée proche de la fin du tableau;

Le code avec la variable supplémentaire est 62% plus rapide, ce
qui est toujours bon à prendre :-)

Protocole:
- Tests fait avec 30 fois 1000 appels dans un tableau
de 10000 éléments, et 3 séries de mesures moyennées.
- Mesures du temps par GetTickCount()
- Temps de boucles mesurés négligeables

Code original: 260 ms (moyenne pour 1000 appels)
Code modifié : 162 ms (moyenne idem )

Ecart type de l'ordre de 8 ms (= +/-la précision GetTickCount)

--
Jean-marc
Tester mon serveur (VB6) => http://myjmnhome.dyndns.org
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr