6
votes

Excel Trouver la vitesse vs. VBA Recherche binaire?

Quelle est la qualité / rapide de la recherche binaire de la recherche vs vba Excel VBA? Ma plate-forme est Office 11 | 2003 et je rechercherai des chaînes contre la colonne A sur trois feuilles de valeurs. Nombre total de lignes ~ 140 000

si la valeur de la bibliothèque et des fonctions dois-je faire référence à faire le tri, puis la recherche binaire? Les chaînes / texte de recherche binaire auraient des problèmes potentiels. P>

... une chose doit être noté. Utilisation de la recherche binaire formules avec triedtextrequires mise en garde. Aladin A., Excel MVP P> blockQuote>

Excel Trouver: P>

Worksheets(1).Range("A:A").Find("PN-String-K9", LookIn:=xlValues, LookAt:=xlWhole)


0 commentaires

4 Réponses :


8
votes

Beaucoup contre mon intuition Une recherche binaire VBA surpasse fortement une trouvaille d'Excel. Au moins avec le scénario ci-dessous où 120 000 chaînes de caractères sont réparties uniformément sur 3 feuilles de calcul.

Excel Trouver prend 1 minute 58 secondes,
VBA La recherche binaire prend 36 secondes sur ma machine particulière. P>

L'avantage de savoir que le texte est en ordre dépasse évidemment l'avantage naturel d'Excel. Notez ALADIN A AVERTISSEMENT DE L'ORDRE DE TRI. P>

Option Explicit

' Call Search to look for a thousand random strings
' in 3 worksheets of a workbook

' requires a workbook with 3 sheets and
' column A populated with values between "00001" to "120000"
' split evenly 40,000 to a worksheet in ascending order.
' They must be text, not numbers.

Private Const NUM_ROWS As Long = 120000
Private Const SHEET_1 As String = "Sheet1"
Private Const SHEET_2 As String = "Sheet2"
Private Const SHEET_3 As String = "Sheet3"

' This uses VBA Binary Search
Public Sub Search()
    Worksheets(SHEET_1).Range("B:B").ClearContents
    Worksheets(SHEET_2).Range("B:B").ClearContents
    Worksheets(SHEET_3).Range("B:B").ClearContents
    DoSearch True       ' change to False to test Excel search
End Sub

' Searches for a thousand values using binary  or excel search depending on
' value of bBinarySearch
Public Sub DoSearch(ByVal bBinarySearch As Boolean)
    Debug.Print Now
    Dim ii As Long

    For ii = 1 To 1000
        Dim rr As Long
        rr = Int((NUM_ROWS) * Rnd + 1)
        If bBinarySearch Then
            Dim strSheetName As String
            Dim nRow As Long
            If BinarySearch(MakeSearchArg(rr), strSheetName, nRow) Then
                Worksheets(strSheetName).Activate
                Cells(nRow, 1).Activate
            End If
        Else
            If Not ExcelSearch(SHEET_1, MakeSearchArg(rr)) Then
                If Not ExcelSearch(SHEET_2, MakeSearchArg(rr)) Then
                    ExcelSearch SHEET_3, MakeSearchArg(rr)
                End If
            End If
        End If
        ActiveCell.Offset(0, 1).Value = "FOUND"
    Next
    Debug.Print Now

End Sub

' look for one cell value using Excel Find
Private Function ExcelSearch(ByVal strWorksheet As String _
  , ByVal strSearchArg As String) As Boolean
    On Error GoTo Err_Exit
    Worksheets(strWorksheet).Activate
    Worksheets(strWorksheet).Range("A:A").Find(What:=strSearchArg, LookIn:=xlValues, LookAt:= 
        xlWhole, SearchOrder:=xlByRows, SearchDirection:=xlNext, MatchCase:=True 
        , SearchFormat:=False).Activate
    ExcelSearch = True
    Exit Function
Err_Exit:
    ExcelSearch = False
End Function

' Look for value using a vba based binary search
' returns true if the search argument is found in the workbook
' strSheetName contains the name of the worksheet on exit and nRow gives the row
Private Function BinarySearch(ByVal strSearchArg As String _
  , ByRef strSheetName As String, ByRef nRow As Long) As Boolean
    Dim nFirst As Long, nLast As Long
    nFirst = 1
    nLast = NUM_ROWS
    Do While True
        Dim nMiddle As Long
        Dim strValue As String
        If nFirst > nLast Then
            Exit Do     ' Failed to find search arg
        End If
        nMiddle = Round((nLast - nFirst) / 2 + nFirst)
        SheetNameAndRowFromIdx nMiddle, strSheetName, nRow
        strValue = Worksheets(strSheetName).Cells(nRow, 1)
        If strSearchArg < strValue Then
            nLast = nMiddle - 1
        ElseIf strSearchArg > strValue Then
            nFirst = nMiddle + 1
        Else
            BinarySearch = True
            Exit Do
        End If
    Loop
End Function

' convert 1 -> "000001", 120000 -> "120000", etc
Private Function MakeSearchArg(ByVal nArg As Long) As String
    MakeSearchArg = Right(CStr(nArg + 1000000), 6)
End Function

' converts some number to a worksheet name and a row number
' This is depenent on the worksheets being named sheet1, sheet2, sheet3

' and containing an equal number of vlaues in each sheet where
' the total number of values is NUM_ROWS
Private Sub SheetNameAndRowFromIdx(ByVal nIdx As Long _
  , ByRef strSheetName As String, ByRef nRow As Long)
    If nIdx <= NUM_ROWS / 3 Then

        strSheetName = SHEET_1
        nRow = nIdx
    ElseIf nIdx > (NUM_ROWS / 3) * 2 Then
        strSheetName = SHEET_3
        nRow = nIdx - (NUM_ROWS / 3) * 2
    Else
        strSheetName = SHEET_2
        nRow = nIdx - (NUM_ROWS / 3)
    End If
End Sub


3 commentaires

Merci. Faire un cas de test de recherche de 1000 exemples à l'intérieur de 52 000 possibilités (feuille unique), j'ai eu 17 secondes pour Excel Trouver contre 5,5 secondes pour la recherche binaire. Le RUB est la recherche binaire a échoué à 25% du temps. Je pense que le problème est que l'excellent tri pour les chaînes est de commander différemment des comparaisons ">" et "<<" de VBA.


Enregistre des enregistrements de coquillage et la recherche binaire fonctionne bien! 2000 exemples aléatoires, où trouvés à partir de 52 000 lignes dans 36Sec (Excel Trouver) contre 11 sec (Recherche binaire).


Remplacement de Middle = rond ((((dernier - premier) / 2 + Nfirst) avec nmiddle = (nlast + nfirst) \ 2 presque double la vitesse de la recherche binaire sur une variante .



3
votes

Je trouve en utilisant l'autofiltre fonctionne beaucoup plus rapidement que de rechercher manuellement les enregistrements avec n'importe quelle méthode.

Je filtre, vérifiez s'il y a des résultats, puis passez à autre chose. Si vous y trouvez (en vérifiant le nombre de résultats), je peux rechercher la petite partie filtrée manuellement ou les renvoyer tous.

Je l'ai utilisé sur environ 44 000 enregistrements, recherchant une liste de plus de 100 pièces contre elle.

Les recherches binaires peuvent facilement être bloquées dans des boucles infinies si vous n'êtes pas prudent.


0 commentaires

3
votes

Si vous utilisez Vlookup avec l'option de tri, il sera probablement plus rapide que votre VBA.


0 commentaires

0
votes

Je suis devenu intéressé par cela parce que j'utilisais la fonction .Find, et sur un PC, il n'a pas réussi à travailler sur certaines recherches, mais sur une autre c'était ok! J'ai donc fait des tests sur des timings - j'ai une feuille avec 985 noms triés dans l'ordre et j'ai écrit un petit sous-programme pour les exécuter, et regardez-le dans la même liste en utilisant une méthode différente ( Les temps sont en millisecondes):

  1. BRUTE FORCE: 2000
  2. .Find: 750
  3. Application.Vlookup: 265
  4. Recherche binaire: 234

    Le problème avec Vlookup est qu'il ne peut pas renvoyer le numéro de ligne, à moins que vous l'incluiez dans votre table.

    Voici mon code pour la recherche binaire, j'ai supposé que La feuille a une ligne d'en-tête, mais vous pouvez facilement modifier l'en-tête et le code pour réussir ces informations. Le paramètre Col en option est utilisé pour indiqué si vous souhaitez le numéro de ligne ou une valeur d'une cellule. La fonction renvoie 0 (zéro) si la recherche échoue. xxx


0 commentaires