Pour vérifier si une chaîne contient un élément d'une liste (de chaînes) - Existe-t-il un meilleur moyen d'écrire ce code?

Question

Pour le bloc de code suivant:

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

La sortie est:

Cas 1:

machaine: C:\Files\myfile.doc

listOfString: C:\Files\, C:\Files2\

Résultat: True

Cas 2:

machaine: C:\Files3\myfile.doc

listOfString: C:\Files\, C:\Files2\

Résultat: False

À tout moment la liste (listOfStrings) peut contenir plusieurs éléments (minimum 20) et elle doit être vérifiée sur des milliers de chaînes de caractères (comme myString).

Est-il mieux (plus efficace) de façon à écrire ce code?

Answer 1

Avec LINQ, et à l'aide de C# (je ne sais pas VB beaucoup ces jours-ci):

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

ou (plus court et plus efficace, mais sans doute moins clair):

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

Si vous ont été de tester l'égalité, il serait intéressant de regarder HashSet etc, mais ce n'est pas aider avec les correspondances partielles, sauf si vous le diviser en fragments et ajouter un ordre de complexité.

---

mise à jour: si tu veux vraiment dire "StartsWith", alors vous pouvez trier la liste et la placer dans un tableau ; ensuite, utilisez Array.BinarySearch trouver chaque élément - vérifier en recherche pour voir si elle est complète ou partielle de la correspondance.

Answer 2

Il y avait un certain nombre de suggestions à partir d'une question similaire,"le Meilleur moyen de tester la chaîne existante contre une grande liste d'éléments de comparaison".

Regex peut-être suffisant pour vos besoins. L'expression serait une concaténation de tous les candidats des sous-chaînes, avec un OU "|" opérateur d'entre eux. Bien sûr, vous aurez à regarder pour sans échappement des caractères lors de la construction de l'expression, ou l'impossibilité de le compiler en raison de la complexité ou des limitations de taille.

Une autre façon de le faire serait de construire un trie de la structure de données pour représenter tous les candidats sous-chaînes (ce qui peut un peu dupliquer ce que la regex matcher est en train de faire). Au fur et à mesure de chaque caractère dans la chaîne de test, vous devez créer un nouveau pointeur sur la racine de la trie, et l'avance des pointeurs existants à la appropriée de l'enfant (le cas échéant). Vous obtenez un match quand tout pointeur atteint une feuille.

Answer 3

Basé sur vos habitudes d'une amélioration consisterait à modifier à l'aide de StartsWith au lieu de les Contient. StartsWith besoin seulement d'itérer sur chaque corde, jusqu'à ce qu'il trouve la première incompatibilité au lieu d'avoir à redémarrer la recherche à chaque position de caractère quand il en trouve un.

Aussi, basé sur vos habitudes, on dirait que vous pourriez être en mesure d'extraire la première partie du chemin d'accès pour myString, puis d'inverser la comparaison -- à la recherche pour le chemin de départ de myString dans la liste de chaînes de caractères plutôt que l'inverse.

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

return listOfStrings.Contains( startPath );

EDIT: Ce serait encore plus vite en utilisant le HashSet idée @Marc Gravel mentionne, car vous pourriez changer d' Contains de ContainsKey et de la recherche serait en O(1) au lieu de O(N). Vous devez assurez-vous que les chemins correspondent exactement. Notez que ce n'est pas une solution générale comme @Marc Gravel, mais est adapté à vos exemples.

Désolé pour l'exemple en C#. Je n'ai pas eu assez de café pour traduire à VB.

Answer 4

Je ne suis pas sûr que ce soit plus efficace, mais vous pouvez penser à utiliser à Lambda Expressions .

Answer 5

Avez-vous testé la vitesse?

Par exemple, avez-vous créé un échantillon de données et l'avez-vous profilé? Ce n'est peut-être pas aussi grave que vous le pensez.

Cela pourrait aussi être quelque chose que vous pourriez engendrer dans un fil séparé et donner l'illusion de vitesse!