XL 2016 VBA - Recherche dichotomique dans une table

Dudu2

XLDnaute Barbatruc
Bonjour,

Je cherche si une valeur existe dans une table triée de 152.000 valeurs.
Le scan jusqu'à valeur <= prend trop de temps car j'ai pas mal de valeurs à chercher.

Pour m'éviter de coder / tester, quelqu'un aurait un petit code VBA pour une recherche dichotomique dans la recherche d'une valeur dans une table triée ?
Merci par avance.
 

mapomme

XLDnaute Barbatruc
Supporter XLD
Bonjour à tous,

Pas assez rapide ;). Rechercher une valeur dans la colonne A de la feuille.
VB:
Sub Rechercher()
Dim ligne&, Achercher
   Achercher = 100
   ligne = Application.Evaluate(Replace("IFERROR(MATCH(xxx,A:A,0),0)", "xxx", Achercher))
   If ligne = 0 Then MsgBox "Pas trouvé" Else MsgBox "Trouvé en ligne " & ligne
End Sub
 

Dranreb

XLDnaute Barbatruc
Bonjour @mapomme
C'est surtout avec 0 en 3ème argument que ça ne vas pas être assez rapide, car pas dichotomique.
Avec 1 j'ai déjà vu des propositions dépasser le Dictionary, mais je ne sais plus si c'était pour plus
de 150 000 éléments.
 
Dernière édition:

GALOUGALOU

XLDnaute Accro
re dudu2 bonjour ma pomme bonjour dranreb, bonjour le forum
j'ai eu l'occasion de me servir de ce code trouvé sur internet, mais comme je n'ai pas vos compétences, je vous le livre tel-quel
VB:
Public Sub tri()
Dim premligne, derligne, lireligne As Double
Dim valeurcherchee As Double
premligne = 1
derligne = 150000
 
valeurcherchee = InputBox("valeur cherchée")
 
If Range("A1").Value > valeurcherchee Then
    MsgBox ("Pas trouvée")
    Exit Sub
End If
 
If Range("A" & derligne).Value < valeurcherchee Then
    MsgBox ("Pas trouvée")
    Exit Sub
End If
While premligne <> derligne - 1
    lireligne = Int((premligne + derligne) / 2)
    Range("A" & lireligne).Select
    If Selection = valeurcherchee Then
        MsgBox ("trouvee en " + CStr(lireligne))
        Exit Sub
        Else
        If Selection > valeurcherchee Then
            derligne = lireligne
            Else
            premligne = lireligne
        End If
    End If
Wend
If Range("A" & premligne).Value = valeurcherchee Then
    MsgBox ("trouvé en " + premligne)
    Else
    If Range("A" & derligne).Value = valeurcherchee Then
        MsgBox ("trouvé en " + derligne)
        Else
        MsgBox ("Non trouvé")
    End If
End If
End Sub
cdt
galougalou
 

Pièces jointes

  • recherche dichotomique .xlsm
    19.8 KB · Affichages: 4

mapomme

XLDnaute Barbatruc
Supporter XLD
C'est surtout avec 0 en 3ème argument que ça ne vas pas être assez rapide, car pas dichotomique.
Avec 1 j'ai déjà vu des propositions dépasser le Dictionary, mais je ne sais plus si c'était pour plus
de 150 000 éléments.
Bonjour @Dranreb :),
Oui avec 1 c'est sûr c'est rapide. Il me semble que si on recherche une valeur qui n'y est pas, avec le paramètre 1, Match peut renvoyer une autre valeur. Il faut donc encore vérifier que la valeur correspondant au Match est égale à celle recherchée.
 

Dranreb

XLDnaute Barbatruc
Oui :
VB:
Function RechDicho(ByVal Arg, ByVal RngCol As Range) As Long
   On Error Resume Next
   RechDicho = WorksheetFunction.Match(Arg, RngCol, 1)
   If Err Then Exit Function
   If RngCol(RechDicho, 1).Value <> Arg Then RechDicho = 0
   End Function
 

job75

XLDnaute Barbatruc
Bonjour à tous,

Testé sur une plage de 152000 cellules :

- liste non triée => EQUIV(xxx;A1:A152000;0) se calcule chez moi en 2,2 millièmes de seconde

- liste triée => EQUIV(xxx;A1:A152000;1) se calcule chez moi en 0,47 millième de seconde.

Edit : En fait j'ai mal testé car il faut déduire le temps mis pour rendre la fonction volatile (0,45 ms).

Avec la liste triée c'est donc de l'ordre de 0,02 milliseconde voire moins.

A+
 
Dernière édition:

Dranreb

XLDnaute Barbatruc
Et que dit le Dictionary avec liaisons anticipées (bibliothèque Scripting, référence Microsoft Scripting Runtime) ? (Sans compter son chargement, évidemment)
Ce serait intéressant de savoir pour combien d'éléments il supplante la recherche dichotomique.
 

Dudu2

XLDnaute Barbatruc
Bonjour et grazie mille a tutti,

Toutes les options proposées sont effectivement possibles.
Pour info je dois passer par un table représentant le Range pour convertir toutes les valeurs en String si elles ne le sont pas déjà pour des raisons obscures de comparaison avec des fichiers d'importation où les chiffres sont en texte.

J'ai finalement choisi la solution Dictionary car elle me permet en plus de conserver une valeur associée.
Je suis impressionné par la rapidité du Dictionary pour lequel j'avais il y a encore peu, bien à tort, un préjugé de lenteur.
<> 0.8 seconde pour le chargement des 152.000 clés (et valeurs associées)
<> 0.5 seconde pour chercher 10.000 items (incluant le stockage en table des items non trouvés)
 

Dranreb

XLDnaute Barbatruc
Quelle est la différence entre Dictionary et Object Dictionary
Avec une variable As Object il est obligé de consacrer un tant soit peu de temps à retrouver la classe associée, et, d'après les noms d'identifiants spécifiés dans le code, les adresses des méthodes de sa programmation et celles des propriétés de son exemplaire avant de pouvoir effectivement exécuter ce qu'on demande. Avec une variable objet de type spécifique tout cela est pré-résolu à la compilation à quelques simples bases ou décalages près.
 

mapomme

XLDnaute Barbatruc
Supporter XLD
Re à tous,

J'ai construit deux procédures de test (encore une fois battu par @Dranreb :mad:;) et qui m'a permis d'arrêter de raconter des conneries sur late and early binding - je croyais que cela n'avait d’influence que sur la création de l'objet mais plus après - merci @Dranreb :)).

J'aboutis à la conclusion: la dichotomie est deux fois plus rapide que le dictionary en late binding et sinon seulement 1,5 fois plus rapide en early binding.

Pour 100.000 recherches, dictionary dure environ 168 milisecondes et dichotomie dure environ 367 milisecondes (late binding) ou bien 270 milisecondes en early binding (aux erreurs de logique de codage près o_O)

Cliquez sur le bouton INIT puis sur chacun des deux autres boutons.

Le résultat des colonnes "IndexDe" est l'index au sein de la plage "A1:A152001" des valeurs de la colonne située juste à gauche. IndexDe vaut 0 si l'élément recherché n'est pas dans la plage "A1:A152001".

v2 => déclaration du dictionary en late bindding ; v2a déclaration du dictionary en early binding
 

Pièces jointes

  • dudu2- Dicho- v2.xlsm
    18.7 KB · Affichages: 7
  • dudu2- Dicho- v2a.xlsm
    18.8 KB · Affichages: 6
Dernière édition:

Discussions similaires

Statistiques des forums

Discussions
311 720
Messages
2 081 909
Membres
101 836
dernier inscrit
karmon