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