Coincidencia de valores en matriz de cadenas

Problema: Buscando una manera más eficiente de encontrar si hay un valor de coincidencia exacto en una matriz de 1d, esencialmente un booleano true/false .

¿Estoy pasando por alto algo obvio? ¿O simplemente estoy usando la estructura de datos incorrecta, usando una matriz cuando probablemente debería estar usando un objeto de colección o un diccionario? En este último, pude verificar el método .Contains o .Exists , respectivamente

En Excel, puedo buscar un valor en una matriz vectorial como:

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

Esto devuelve un índice de coincidencia exacta, obviamente sujeto a las limitaciones de la función de Match que solo encuentra el primer valor coincidente en este contexto. Este es un método de uso común, y uno que he estado usando durante mucho tiempo también.

Esto es lo suficientemente satisfactorio para Excel, pero ¿qué pasa con otras aplicaciones?

En otras aplicaciones, puedo hacer básicamente lo mismo, pero es necesario habilitar la referencia a la biblioteca de objetos de Excel, y luego:

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

Sin embargo, parece una tontería y es difícil de administrar en archivos distribuidos debido a permisos / centro de confianza / etc.

He intentado usar la función Filter () :

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

Pero el problema con este enfoque es que Filter devuelve una matriz de coincidencias parciales, en lugar de una matriz de coincidencias exactas. (No tengo idea de por qué sería útil devolver subcadenas / coincidencias parciales).

La otra alternativa es iterar literalmente sobre cada valor de la matriz (creo que esto también se usa con mucha frecuencia), lo que parece aún más engorroso e innecesario que invocar la función de Match de Excel.

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

Si vamos a hablar sobre el rendimiento, entonces no hay substutute para ejecutar algunas pruebas. En mi experiencia, Application.Match () es hasta diez veces más lento que llamar a una función que utiliza un bucle.

 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 

Salida:

 Contains 0.8710938 Match 4.210938 

Solía ​​buscar la mejor solución de reemplazo. Debería funcionar para un simple hallazgo también.

Para encontrar la primera instancia de una cadena, puede intentar usar este código:

 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 

Si quieres encontrar todas las instancias, prueba lo siguiente.

 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 

Tenga en cuenta que si hay varias instancias de cadenas buscadas dentro de una celda, solo obtendrá un resultado debido a la especificación de FindNext.

Aún así, si necesita un código para reemplazar los valores encontrados con otro, usaría la primera solución, pero tendría que cambiarla un poco.

“Una forma más eficiente (en comparación con Application.Match ) de encontrar si existe un valor de cadena en una matriz”:

Creo que no hay una manera más eficiente que la que está utilizando, es decir, Application.Match .

Las matrices permiten un acceso eficiente en cualquier elemento si conocemos el índice de ese elemento. Si queremos hacer algo por valor de elemento (incluso comprobando si existe un elemento), tenemos que escanear todos los elementos de la matriz en el peor de los casos. Por lo tanto, el peor caso necesita n comparaciones de elementos, donde n es el tamaño de la matriz. Entonces, el tiempo máximo que necesitamos encontrar si un elemento existe es lineal en el tamaño de la entrada, es decir, O(n) . Esto se aplica a cualquier lenguaje que use arreglos convencionales.

El único caso en el que podemos ser más eficientes es cuando la matriz tiene una estructura especial. Para su ejemplo, si los elementos de la matriz están ordenados (por ejemplo, alfabéticamente), entonces no es necesario que escaneemos toda la matriz: lo comparamos con el elemento medio y luego lo comparamos con la parte izquierda o derecha de la matriz ( búsqueda binaria) ) Pero sin asumir ninguna estructura especial, no hay esperanza …

El Dictionary/Collection como señala, ofrece acceso de clave constante a sus elementos ( O(1) ). Lo que quizás no está muy bien documentado es que también se puede tener acceso de índice a los elementos del diccionario (claves y elementos): se conserva el orden en que se ingresan los elementos en el Dictionary . Su principal desventaja es que usan más memoria ya que se almacenan dos objetos para cada elemento.

Para concluir, aunque If Not IsError(Excel.Application.match(...)) parece tonto, sigue siendo la forma más eficiente (al menos en teoría). En cuestiones de permisos, mi conocimiento es muy limitado. Dependiendo de la aplicación de host, siempre hay algunas funciones de find_if de find_if ( C++ tiene find y find_if por ejemplo).

¡Espero que eso ayude!

Editar

Me gustaría añadir un par de ideas después de leer la versión modificada de la publicación y la respuesta de Tim. El texto anterior se centra en la complejidad del tiempo teórico de las diversas estructuras de datos e ignora los problemas de implementación. Creo que el espíritu de la pregunta era más bien “dada una cierta estructura de datos (matriz)”, cuál es la forma más eficaz en la práctica de verificar la existencia.

Con este fin, la respuesta de Tim es una revelación.

La regla convencional “si VBA puede hacerlo por ti, entonces no la vuelvas a escribir tú mismo” no siempre es verdad. Operaciones simples como bucles y comparaciones pueden ser más rápidas que “aceptar” funciones de VBA . Dos enlaces interesantes están aquí y aquí .