Comprobar si una cadena contiene un elemento de una lista (de cadenas)

Question

Para el siguiente bloque de código:

For I = 0 To listOfStrings.Count - 1 
    If myString.Contains(lstOfStrings.Item(I)) Then 
     Return True 
    End If 
Next 
Return False 

La salida es:

Caso 1:

myString: C:\Files\myfile.doc 
listOfString: C:\Files\, C:\Files2\ 
Result: True 

Caso 2:

myString: C:\Files3\myfile.doc 
listOfString: C:\Files\, C:\Files2\ 
Result: False 

La lista (listOfStrings) puede contener varios elementos (mínimo 20) y se debe comparar con miles de cadenas (como myString).

¿Existe alguna forma mejor (más eficiente) de escribir este código?

Answer 1

Con LINQ, y el uso de C# (no sé VB mucho en estos días):

bool b = listOfStrings.Any(s=>myString.Contains(s)); 

o (más corto y más eficiente, pero sin duda menos claro):

bool b = listOfStrings.Any(myString.Contains); 

Si estaba probando la igualdad, valdría la pena mirar HashSet etc., pero esto no ayudará con las coincidencias parciales a menos que lo divida en fragmentos y agregue un orden de complejidad.

---

actualización: si realmente quiere decir "StartsWith", podría ordenar la lista y colocarla en una matriz; luego, use Array.BinarySearch para encontrar cada elemento - verifique por búsqueda para ver si es una coincidencia total o parcial.

Answer 2

No estoy seguro si es más eficiente, pero podría pensar en usar en Lambda Expressions.

Answer 3

Hubo una serie de sugerencias de una pregunta similar anterior "Best way to test for existing string against a large list of comparables".

Regex puede ser suficiente para su requerimiento. La expresión sería una concatenación de todas las subcadenas candidatas, con un operador OR "|" entre ellas. Por supuesto, tendrá que tener cuidado con los caracteres no escaneados al crear la expresión, o si no los compila debido a limitaciones de complejidad o tamaño.

Otra forma de hacer esto sería construir un trie data structure para representar todas las subcadenas candidatas (esto puede duplicar un poco lo que está haciendo el corrector de expresiones regulares). A medida que avanza por cada carácter en la cadena de prueba, debe crear un nuevo puntero a la raíz del trie y avanzar los punteros existentes al niño apropiado (si corresponde). Obtienes una coincidencia cuando cualquier puntero alcanza una hoja.

Answer 4

En función de sus patrones, una mejora sería cambiar a utilizar StartsWith en lugar de Contiene. StartsWith solo necesita iterar a través de cada cadena hasta que encuentre la primera falta de coincidencia en lugar de tener que reiniciar la búsqueda en cada posición de personaje cuando encuentre una.

Además, según sus patrones, parece que puede extraer la primera parte de la ruta de myString, luego invierta la comparación, buscando la ruta de inicio de myString en la lista de cadenas en lugar de la otro camino alrededor.

string[] pathComponents = myString.Split(Path.DirectorySeparatorChar); 
string startPath = pathComponents[0] + Path.DirectorySeparatorChar; 

return listOfStrings.Contains(startPath); 

EDITAR: Esto sería aún más rápido usando la idea HashSet @Marc Gravell menciona ya que es posible cambiar Contains-ContainsKey y las operaciones de búsqueda sería O (1) en lugar de O (N). Debería asegurarse de que las rutas coincidan exactamente. Tenga en cuenta que esta no es una solución general como la de @Marc Gravell, pero está adaptada a sus ejemplos.

Disculpe por el ejemplo de C#. No he tenido suficiente café para traducir a VB.

Answer 5

Si la velocidad es crítica, es posible que desee buscar el Aho-Corasick algorithm para conjuntos de patrones.

Es un trie con enlaces de falla, es decir, la complejidad es O (n + m + k), donde n es la longitud del texto de entrada, m la longitud acumulada de los patrones yk el número de coincidencias. Solo tiene que modificar el algoritmo para terminar después de que se encuentre la primera coincidencia.

Answer 6

¿Has probado la velocidad?

es decir, ¿ha creado un conjunto de datos de muestra y lo ha perfilado? Puede que no sea tan malo como piensas.

¡Esto también podría ser algo que podría engendrarse en un hilo separado y dar la ilusión de velocidad!

Answer 7

myList.Any(myString.Contains); 

Answer 8

Me gustó la respuesta de Marc, pero necesitaba que el Contiene que coincida con ser CAUSE InSenSiTiVe.

Esta fue la solución:

bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0)) 

Answer 9

al construir el suyo cuerdas debe ser así

bool inact = new string[] { "SUSPENDARE", "DIZOLVARE" }.Any(s=>stare.Contains(s));