Два совета VBA для проверки данных Excel за O(n)

Все дело в структурах данных

Мы часто автоматизируем проверку данных, чтобы повысить эффективность и точность. По крайней мере, так было в моем проекте, где, не имея более сложных опций, мне пришлось писать макросы Excel, чтобы они выполняли работу за меня и мою команду, пока мы занимаемся тестированием системы и переносом данных.

Если вы новичок в VBA, вы можете подумать, что линейный поиск — единственный способ добиться цели. Но если вы работаете с электронными таблицами, это означает, что вы, вероятно, будете осуществлять линейный поиск (или итерацию) по строкам и столбцам — это уже O(n²)!

Правда в том, что у тебя есть варианты получше, фам.

Итак, садитесь, откройте редактор Visual Basic и давайте начнем с большого O.

Сводная проверка данных

На высоком уровне проверка данных состоит из двух подпроцессов:

1. Получение фактических и ожидаемых данных.
2. Сравнение фактического с ожидаемым.

В Excel VBA первый из них может подразумевать чтение данных из электронной таблицы или базы данных, тогда как последний может включать проверку равенства или принадлежности к набору ожидаемых данных.

Совет № 1: Уменьшите число чтений с помощью матриц

При запуске VBA мы изучаем следующий синтаксис для доступа к данным:

Dim wks As Worksheet
Dim val As String
Set wks = ThisWorkbook.Sheets("Sheet1")
val = wks.Range("A1").Value

Конечно, маловероятно, что наш поиск данных остановится на этом. В моем примере используется только первая строка, но нам, вероятно, придется перебрать несколько строк в нашем объекте wks и, возможно, даже столбцы, кроме «A».

Даже если мы можем мириться с O(n²) и небрежным кодом, который, вероятно, связан с ним, мы должны отметить, что чтение данных из файла, такого как электронная таблица Excel, является процессом, связанным с вводом-выводом. Таким образом, каждая ячейка, которую мы итерируем, замедляет время выполнения. В сочетании с плохим алгоритмом мы могли бы съесть полный курс еды (или два), ожидая завершения нашего макроса.

Вместо этого лучше один раз прочитать (и бежать куда угодно — пардон, явская шутка). И, на самом деле, мы можем! Нам просто нужно знать размеры наших табличных данных и позаимствовать возможности типа данных Variant.

Предполагая, что наша таблица охватывает столбцы A и E и состоит из 10 строк, все, что нам нужно, это следующее:

Dim valMatrix As Variant
Dim startRow As Long, numRows As Long
startRow = 2
numRows = 10
valMatrix = wks.Range("A" & startRow, "E" & (startRow + numRows - 1)).Value

В Excel это будет выглядеть примерно так:

И это все. Мы фактически загрузили все данные в valMatrix, который ведет себя как двумерная матрица. То есть мы можем индексировать и перебирать его столбцы и строки как таковые:

Dim val As String
Dim row As Long, col As Long
' LBound and UBound return the lowest and highest index of an index,
' respectively. The second argument specifies the array dimension
' we're interested in.
For row = LBound(valMatrix, 1) To UBound(valMatrix, 1)
  For col = LBound(valMatrix, 2) To UBound(valMatrix, 2)
    Debug.Print valMatrix(row, col)
  Next col
Next row

Благодаря этому мы можем беспрепятственно получать доступ к нашим данным, не увязая в нашей среде выполнения с дорогостоящими операциями чтения электронных таблиц, связанными с вводом-выводом.

Совет № 2: Преобразуйте эту матрицу в словарь

Хорошо, что мы загрузили нашу электронную таблицу в память, но с точки зрения временной сложности желать лучшего не приходится.

Матрицы не идеальны

Чтобы сверить n количество точек данных с электронной таблицей, мы должны пройти через вложенный цикл, который равен O(n²). Таким образом, наше время выполнения может быть O(n³) в худшем случае. Фу.

Однако в реалистичном сценарии наши столбцы, скорее всего, представляют отдельные атрибуты, и мы будем знать необходимые столбцы заранее. Мы не будем перебирать столбцы, и для каждой точки данных мы сможем индексировать соответствующий столбец. Итак, мы исключаем один цикл, и у нас остается O(n²). Еще фу.

Несмотря на ловкость трюка № 1, правда в том, что мы можем достичь O(n) — или чего-то близкого к нему — если мы не сравниваем матрицу с матрицей напрямую.

Достать словари

Вместо этого мы можем позаимствовать возможности структуры данных Dictionary. Словари, основанные на хеш-таблицах, имеют хэш-функцию, которая позволяет им извлекать данные почти за O(1) в большинстве практических ситуаций.

В то время как словари легко доступны на таких языках, как Python, для VBA нам придется сначала добавить ссылку на библиотеку Microsoft Scripting Runtime. После того, как этот шаг будет выполнен, добавление пар ключ-значение станет легкой задачей.

Dim dict As New Dictionary
Dim k As String, v As Integer
k = "test key"
v = "test value"
' Always good to check for key collisions to prevent runtime errors
If dict.Exists(k) = False Then
  dict.Add k, v
End If

Как указано в приведенном выше фрагменте, словарь VBA поставляется с удобным методом Exists, который возвращает логическое значение, которое мы можем использовать для проверки того, существуют ли наши фактические данные в определенном наборе ожидаемых данных.

Конечно, этот совет не сработает, если наши данные не находятся хотя бы во второй нормальной форме, где у нас есть какой-то уникальный ключ для идентификации каждой ожидаемой и фактической записи данных. Это подчеркивает ценность знания данных до начала разработки.

Собираем все вместе

Таким образом, мы можем получить алгоритм проверки данных, близкий к O(n), следующим образом:

1. Сокращение операций чтения, связанных с вводом-выводом, за счет загрузки данных электронной таблицы в матрицу типа Variant.
2. Проверка наших данных с использованием хэш-функции, присущей структуре данных Dictionary. В то время как проверка по электронной таблице может быть O(n) в практических сценариях, этот шаг можно улучшить до O(1).

Таким образом, у нас остается:

Код может выглядеть примерно так:

Public Sub Main()
  ' Let's assume the user provides us a target column 
  ' of unique keys to validate
  Dim targetCol As Long
  targetCol = CLng(Sheets(1).Range("A1").Value)
  If CompareActualExpected(targetCol) = True Then
    Debug.Print 0 ' All data is valid
  Else
    Debug.Print 1 ' Found at least one invalid data point
  End If
End Sub
Private Function CompareActualExpected(targetCol As Long) As Boolean
  Dim expectedValDict As Dictionary, actualValDict As Dictionary
  Dim expSheetName As String, actSheetName As String
  expSheetName = "EXPECTED"
  actSheetName = "ACTUAL"
  Set expectedValDict = _
    GetDictFromMatrix(GetDataAsMatrix(expSheetName), targetCol)
  Set actualValDict = _
    GetDictFromMatrix(GetDataAsMatrix(actSheetName), targetCol)
  ' Compare actual values against the set of expected;
  ' exit function if invalid data point found.
  ' We can use For Each syntax to loop through each key.
  Dim k As Variant
  For Each k In actualValDict
    If expectedValDict.Exists(k) = False Then
        CompareActualExpected = False
        Exit Function
    End If
  Next k
  CompareActualExpected = True
End Function
Private Function GetDataAsMatrix(sheetName As String) As Variant
  ' CurrentRegion selects a entire contiguous range all at once!
  GetDataAsMatrix = _
    Sheets(sheetName).Range("A1").CurrentRegion.Value
End Function
Private Function GetDictFromMatrix(sheetMtrx As Variant, targetCol As Long) As Dictionary
  Dim dict As New Dictionary
  Dim row As Long
  Dim currVal As String
  ' Let's iterate over the rows of the matrix   
  ' and add the values of the target column to the dictionary
  For row = LBound(sheetMtrx, 1) To UBound(sheetMtrx, 1)
    currVal = sheetMtrx(row, targetCol)
    If dict.Exists(currVal) = False Then
      dict.Add currVal, Nothing    
    End If
  Next row
    
  Set GetDictFromMatrix = dict
End Function

Как это О(n)?

1. GetDataAsMatrix равно O(1), предполагая, что свойство Value многоячеечного Range не реализует под капотом алгоритм с более низким временем выполнения.
2. GetDictFromMatrix равно O(n), учитывая, что мы перебираем n строк матрицы, что занимает O(1) согласно #1.
3. CompareActualExpected равно O(n), так как дважды вызывает GetDictFromMatrix, функцию O(n). Конечно, на самом деле это O(2n); но мы можем исключить константу 2.
4. Main равен O(n), так как он вызывает CompareActualExpected и возвращает логическое значение в виде целочисленного кода выхода, 0 (пройдено) или 1 (не пройдено).

Резюме

Когда мы новичок в VBA, мы склонны искать рудиментарные методы, которые кажутся безобидными, пока они не превратят наш код в спагетти и не сделают нашу среду выполнения заоблачной.

С типом данных Variant мы получаем многомерный массив значений ячеек и сокращаем дорогостоящее чтение рабочего листа до одного чтения.

Предполагая, что у нас есть уникальные ключи, все, что осталось, — это проверить принадлежность фактических точек данных к набору ожидаемых значений.

В несортированных данных, где O(n⋅log(n)) из бинарного поиска недостижимо, мы можем прибегнуть к повторению каждого столбца и строки — вложенный цикл O(n²). Но мы не обязаны. Словарь VBA удобен с методом Exists , который проверяет наши данные для нас. Все, что нам нужно сделать, это понять наши данные и попробовать.