Verifique se uma string contém um elemento de uma lista (de strings)

155

Para o seguinte bloco de código:

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

A saída é:

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

A lista (listOfStrings) pode conter vários itens (no mínimo 20) e deve ser verificada em milhares de strings (como myString).

Existe uma maneira melhor (mais eficiente) de escrever esse código?

user57175
fonte

Respostas:

359

Com o LINQ e usando C # (atualmente não conheço muito o VB):

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

ou (mais curto e mais eficiente, mas sem dúvida menos claro):

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

Se você estivesse testando a igualdade, valeria a pena examinar HashSetetc, mas isso não ajudará em correspondências parciais, a menos que você a divida em fragmentos e adicione uma ordem de complexidade.


update: se você realmente quer dizer "StartsWith", pode ordenar a lista e colocá-la em uma matriz; use Array.BinarySearchpara encontrar cada item - verifique com uma consulta para ver se é uma correspondência completa ou parcial.

Marc Gravell
fonte
1
Em vez de Contém, eu usaria StartsWith com base em seus exemplos.
Tvanfosson 01/02/09
@tvanfosson - isso depende se os exemplos são totalmente inclusivos, mas sim, eu concordo. Simples de mudar, é claro.
Marc Gravell
Até que ponto esse código é mais eficiente no nível algorítmico? É mais curto e mais rápido se os loops em "Qualquer" forem mais rápidos, mas o problema de que você precisa executar a correspondência exata muitas vezes é o mesmo.
213 Torsten Marek
Você pode configurar um comparador personalizado se estiver usando um conjunto.
Fortyrunner 01/02/09
O segundo não é realmente mais eficiente por qualquer diferença mensurável na prática.
ICR
7

quando você constrói suas cordas, deve ser assim

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

Houve várias sugestões de uma pergunta semelhante anterior " Melhor maneira de testar a cadeia existente em uma grande lista de comparáveis ".

Regex pode ser suficiente para sua exigência. A expressão seria uma concatenação de todas as substrings candidatas, com um |operador OR " " entre elas. Obviamente, você deve ter cuidado com caracteres não escapados ao criar a expressão ou com uma falha na compilação devido a limitações de complexidade ou tamanho.

Outra maneira de fazer isso seria construir uma estrutura de dados trie para representar todas as substrings candidatas (isso pode duplicar o que o correspondente do regex está fazendo). À medida que você percorre cada caractere na sequência de teste, você cria um novo ponteiro para a raiz da árvore e avança os ponteiros existentes para o filho apropriado (se houver). Você obtém uma correspondência quando qualquer ponteiro atinge uma folha.

Zach Scrivena
fonte
5

Gostei da resposta de Marc, mas precisava da correspondência Contains para ser CaSe InSenSiTiVe.

Esta foi a solução:

bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0))
WhoIsRich
fonte
Não deveria ser> -1?
CSharped
1
@CSharped Não importa, pois> -1 (mais que menos 1) e> = 0 (mais ou igual a zero) são a mesma coisa.
WhoIsRich
2

Com base em seus padrões, uma melhoria seria mudar para o uso de StartsWith em vez de Contains. StartsWith precisa apenas percorrer cada sequência até encontrar a primeira incompatibilidade, em vez de ter que reiniciar a pesquisa em todas as posições de caracteres quando encontrar uma.

Além disso, com base em seus padrões, parece que você pode extrair a primeira parte do caminho para myString e reverter a comparação - procurando o caminho inicial de myString na lista de strings e não o contrário.

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

return listOfStrings.Contains( startPath );

EDIT : Isso seria ainda mais rápido usando a idéia do HashSet que @Marc Gravell menciona, já que você pode mudar Containspara ContainsKeye a pesquisa seria O (1) em vez de O (N). Você precisaria garantir que os caminhos correspondam exatamente. Observe que essa não é uma solução geral, como é a de @Marc Gravell, mas é adaptada aos seus exemplos.

Desculpe pelo exemplo de C #. Não tomei café suficiente para traduzir para o VB.

tvanfosson
fonte
Re começa com; talvez pré-classifique e use a pesquisa binária? Isso pode ser mais rápido novamente.
Marc Gravell
2

Pergunta antiga. Mas desde que VB.NETera o requisito original. Usando os mesmos valores da resposta aceita:

listOfStrings.Any(Function(s) myString.Contains(s))
Luis Lavieri
fonte
1

Você já testou a velocidade?

Você criou um conjunto de dados de amostra e criou um perfil? Pode não ser tão ruim quanto você pensa.

Isso também pode ser algo que você pode gerar em um segmento separado e dar a ilusão de velocidade!

Fortyrunner
fonte
0

Se a velocidade for crítica, convém procurar o algoritmo Aho-Corasick para obter conjuntos de padrões.

É um experimento com links de falha, ou seja, a complexidade é O (n + m + k), onde n é o comprimento do texto de entrada, m o comprimento acumulado dos padrões e k o número de correspondências. Você apenas precisa modificar o algoritmo para finalizar após a primeira correspondência ser encontrada.

Torsten Marek
fonte
0
myList.Any(myString.Contains);
WIRN
fonte
0

A desvantagem do Containsmétodo é que ele não permite especificar o tipo de comparação que geralmente é importante na comparação de strings. É sempre sensível à cultura e ao caso. Então, acho que a resposta do WhoIsRich é valiosa, só quero mostrar uma alternativa mais simples:

listOfStrings.Any(s => s.Equals(myString, StringComparison.OrdinalIgnoreCase))
Al Kepp
fonte