Использование бинарного поиска в массиве вариантов, созданном из набора записей ADO - PullRequest
Новая
       8

Использование бинарного поиска в массиве вариантов, созданном из набора записей ADO

0 голосов
/ 26 февраля 2011

Я использую VB6 (да, я знаю), чтобы получить набор записей ADO (более 650 000 записей) и загрузить этот набор записей в массив вариантов. Затем я пытаюсь найти массив, чтобы увидеть, существует ли в нем указанное строковое значение, используя функцию бинарного поиска, которую я нашел в Интернете. Я получаю сообщение об ошибке «Subscript Out of Range» при вызове функции двоичного поиска. Есть идеи, что я здесь не так делаю? 

Dim arrItems() As Variant
'gXRst and gXCon are global variables declared elsewhere. They are not the problem here.
With gXRst
    .CursorLocation = adUseClient
    .CursorType = adOpenKeyset
    .LockType = adLockReadOnly
    .Open "SELECT item_cd FROM xmsalinv ORDER BY item_cd ASC", gXCon
End With

arrItems = gXRst.GetRows(gXRst.RecordCount)
gXRst.Close
MsgBox BinarySearch(arrItems(), "491588S")

Function BinarySearch(arr As Variant, search As String, _
    Optional lastEl As Variant) As Long
    Dim index As Long
    Dim first As Long
    Dim last As Long
    Dim middle As Long
    Dim inverseOrder As Boolean

    ' account for optional arguments
    If IsMissing(lastEl) Then lastEl = UBound(arr)

    first = LBound(arr)
    last = lastEl

    'Error message occurring on next line. Error 9, subscript out of range.
    ' deduct direction of sorting
    inverseOrder = (arr(first) > arr(last))

    ' assume searches failed
    BinarySearch = first - 1

    Do
        middle = (first + last) \ 2
        If arr(middle) = search Then
            BinarySearch = middle
            Exit Do
        ElseIf ((arr(middle) < search) Xor inverseOrder) Then
            first = middle + 1
        Else
            last = middle - 1
        End If
    Loop Until first > last
End Function

Ответы [ 2 ]

1 голос
/ 26 февраля 2011

В дикой природе существует множество неуклюжих сортов, закодированных вручную, у многих есть тонкие ошибки, и большинство из них являются "игрушечными", сортирующими одномерный массив.Многие из них являются продуктом "скоростных уродов", которые редко создают настоящую программу, но получают удовольствие от работы.Следите за ошибками "off by one" во многих подпрограммах двоичного поиска, которые вы также можете найти там (например, не можете обрабатывать четные или нечетные числа для элементов).

Вы уже "потратили" ресурсысоздание набора записей, поэтому рассмотрите возможность его использования с настройкой.

Использование Optimize:

Вы можете улучшить производительность gXRst.Find, используя курсор на стороне клиента, правильный CursorType и создавИндексы используемых ключей (ключей) (Оптимизировать динамическое свойство): 

With gXRst
    .CursorLocation = adUseClient
    .Open "SELECT item_cd FROM xmsalinv ORDER BY item_cd ASC", _
          gXCon, adOpenStatic, adLockReadOnly, adCmdText
    !item_cd.Properties("Optimize") = True
End With

Найти первым: 

gXRst.Find "item_cd = '4915885'", , adSearchForward, adBookMarkFirst

Найти следующим: 

gXRst.Find "item_cd = '4915885'", 1, adSearchForward, adBookMarkCurrent

Найти последнее: 

gXRst.Find "item_cd = '4915885'", , adSearchBackward, adBookMarkLast

Конечно, отметив, что текущая позиция строки должна быть установлена ​​перед вызовом Find.В случае сомнений используйте MoveFirst, MoveLast и т. Д. Или используйте значения BookMark для начала с первого / последнего (по умолчанию adBookMarkCurrent).

Из презентации PowerPoint (около 1999 г.) Отключение ADO Роб Макдональд: 

Data Structures Compared

Figures below are based on a 5000 row, 4 column data structure.
    * Times are normalised on Variant Array performance
    * Array sorting is 400 times slower than iteration

            Variant Array Recordset Indexed Recordset Collection
----------- ------------- --------- ----------------- -----------
Iterate     100           2,120     2,160                 120
Find 1 (1)  100             308         2.6           0.9/212 (2)
Find n (1)  100             422        17                 393
Sort (1)    100               3.2       3.0             7,076

    (1) timings include iterating through the results
    (2) the faster time is achieved if searching by collection key is possible
1 голос
/ 26 февраля 2011

GetRows возвращает двумерный массив , но программе двоичного поиска требуется массив 1D.

Почему бы просто не использовать встроенный Find в объекте набора записей? Это быстрее, чем ручной бинарный поиск, и намного проще. 

gXRst.MoveFirst
gXRst.Find("item_cd='491588S'")
MsgBox gXRst.Fields("item_cd").Value
...