Соответствующие значения в строковом массиве

Question

Проблема: поиск более эффективного способа нахождения точного значения соответствия в массиве 1d - по существу булево true/false.

Могу ли я пропустить что-то очевидное? Или я просто использую неправильную структуру данных, используя массив, когда я, вероятно, должен использовать объект коллекции или словарь? В последнем случае я мог проверить .Contains или .Exists метод, соответственно

В Excel я могу проверить для значения в векторном массиве как:

If Not IsError(Application.Match(strSearch, varToSearch, False)) Then 
' Do stuff 
End If 

Это возвращает точный индекс соответствия, очевидно, при условии соблюдения ограничений Match Функция, которая находит только Соответствующее значение в этом контексте. Это обычно используемый метод, и тот, который я использовал в течение длительного времени.

Это достаточно удовлетворительно для Excel - но как насчет других приложений?

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

If Not IsError(Excel.Application.match(...)) 

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

Я пытался использовать Filter() функции:

If Not Ubound(Filter(varToSearch, strSearch)) = -1 Then 
    'do stuff 
End If 

Но проблема такого подхода заключается в том, что Filter возвращает массив частичных совпадений, а не массив точных совпадений. (Я не знаю, почему было бы полезно возвращать подстроки/частичные совпадения.)

Другой альтернативой является буквально перебирать каждое значение в массиве (это также очень часто используется, я думаю) - что кажется даже более бесполезно громоздко, чем вызов функции Excel Match.

For each v in vArray 
    If v = strSearch Then 
    ' do stuff 
    End If 
Next 

Answer 1

Если мы поговорим о производительности, тогда нет никаких подстановок для запуска некоторых тестов. По моему опыту Application.Match() работает до десяти раз медленнее вызова функции, которая использует цикл.

Sub Tester() 

    Dim i As Long, b, t 
    Dim arr(1 To 100) As String 

    For i = 1 To 100 
     arr(i) = "Value_" & i 
    Next i 

    t = Timer 
    For i = 1 To 100000 
     b = Contains(arr, "Value_50") 
    Next i 
    Debug.Print "Contains", Timer - t 

    t = Timer 
    For i = 1 To 100000 
     b = Application.Match(arr, "Value_50", False) 
    Next i 
    Debug.Print "Match", Timer - t 

End Sub 


Function Contains(arr, v) As Boolean 
Dim rv As Boolean, lb As Long, ub As Long, i As Long 
    lb = LBound(arr) 
    ub = UBound(arr) 
    For i = lb To ub 
     If arr(i) = v Then 
      rv = True 
      Exit For 
     End If 
    Next i 
    Contains = rv 
End Function 

Выход:

Contains  0.8710938 
Match   4.210938 

Answer 2

Раньше я искал лучшее решение для замены. Он должен работать и для простого поиска.

Чтобы найти первый экземпляр строки вы можете попробовать использовать этот код:

Sub find_strings_1() 

Dim ArrayCh() As Variant 
Dim rng As Range 
Dim i As Integer 

ArrayCh = Array("a", "b", "c") 

With ActiveSheet.Cells 
    For i = LBound(ArrayCh) To UBound(ArrayCh) 
     Set rng = .Find(What:=ArrayCh(i), _ 
     LookAt:=xlPart, _ 
     SearchOrder:=xlByColumns, _ 
     MatchCase:=False) 

     Debug.Print rng.Address 

    Next i 
End With 

End Sub 

Если вы хотите, чтобы найти все экземпляры попробовать ниже.

Sub find_strings_2() 

Dim ArrayCh() As Variant 
Dim c As Range 
Dim firstAddress As String 
Dim i As Integer 

ArrayCh = Array("a", "b", "c") 'strings to lookup 

With ActiveSheet.Cells 
    For i = LBound(ArrayCh) To UBound(ArrayCh) 
     Set c = .Find(What:=ArrayCh(i), LookAt:=xlPart, LookIn:=xlValues) 

     If Not c Is Nothing Then 
      firstAddress = c.Address 'used later to verify if looping over the same address 
      Do 
       '_____ 
       'your code, where you do something with "c" 
       'which is a range variable, 
       'so you can for example get it's address: 
       Debug.Print ArrayCh(i) & " " & c.Address 'example 
       '_____ 
       Set c = .FindNext(c) 

      Loop While Not c Is Nothing And c.Address <> firstAddress 
     End If 
    Next i 
End With 

End Sub 

Имейте в виду, что при наличии нескольких экземпляров искали строки в одной ячейке он будет возвращать только один результат из-за специфики FindNext.

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

Answer 3

«Более эффективный способ (по сравнению с Application.Match) найти, существует ли значение строки в массиве»:

Я считаю, что нет более эффективный способ, чем тот, который вы используете, то есть, Application.Match.

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

Единственный случай, когда мы можем быть более эффективными, - это когда массив имеет специальную структуру. Для вашего примера, если элементы массива отсортированы (например, в алфавитном порядке), нам не нужно сканировать весь массив: мы сравниваем его с средним элементом, а затем сравниваем с левой или правой частью массива (binary search). Но, не предполагая никакой специальной структуры, нет никакой надежды ..

Dictionary/Collection, как вы указываете, предлагает постоянный ключ доступа к их элементам (O(1)). то, что, возможно, не очень хорошо документирована, что один может также иметь доступ указательный Элементы словаря (Ключи и элементы): порядок, в котором элементы введены в Dictionary, сохраняется. Их основным недостатком является то, что они используют больше памяти, поскольку для каждого элемента хранятся два объекта.

Чтобы обернуть, хотя If Not IsError(Excel.Application.match(...)) выглядит глупо, это все же более эффективный способ (по крайней мере, в теории). По вопросам разрешения мои знания очень ограничены. В зависимости от приложения-хоста всегда есть некоторые функции Find (C++ имеет find и find_if например).

Я надеюсь, что это поможет!

Редактировать

Я хотел бы добавить несколько мыслей, после прочтения исправленной версии поста и ответа Тима. В приведенном выше тексте основное внимание уделяется теоретической сложности времени различных структур данных и игнорируется проблемы реализации. Я думаю, что дух вопроса был скорее «с учетом определенной структуры данных (массива)», что наиболее эффективным способом является на практике проверки существования.

С этой целью ответ Тима является открытием.

Обычное правило «если VBA может сделать это за вас, то не пишите его снова самостоятельно», это не всегда так. Простые операции, такие как циклизация и сравнение, могут быть быстрее, чем функции «соглашаться» VBA. Две интересные ссылки: here и here.