XL 2016 VBA - Recherche dichotomique dans une table

[Dudu2]

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.

 

[Dranreb]

Bonjour.
Le mieux c'est d'utiliser WorkhsheetFunction.Match(Arg, Plage, 1)

 

[mapomme]

Bonjour à tous,

Pas assez rapide . Rechercher une valeur dans la colonne A de la feuille.

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]

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.

 

[GALOUGALOU]

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

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

 

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

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]

Oui :

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]

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+

 

[Dranreb]

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]

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]

Tests Match(,,0), Match(,,1), Dictionary, Object Dictionary et Collection.

 

[Dudu2]

Intéressant !
Quelle est la différence entre Dictionary et Object Dictionary ?
Early (avec “Microsoft Scripting Runtime”) and late binding ?

 

[job75]

J'ai édité mon post #8, avec EQUIV'(xxx;A1:A152000;1) c'est beaucoup plus rapide.

 

[Dranreb]

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]

Re à tous,

J'ai construit deux procédures de test (encore une fois battu par @Dranreb 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 )

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