Prüfen, ob eine Zeichenkette, ein Element aus einer Liste enthält (von Strings)

Question

Für den folgenden Code-Block:

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

Der Ausgang ist:

Fall 1:

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

Fall 2:

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

Die Liste (listOfStrings) kann mehrere Elemente (mindestens 20) enthalten und muss gegen Tausende von Strings (wie myString) geprüft werden.

Gibt es eine bessere (effizientere) Möglichkeit, diesen Code zu schreiben?

Answer 1

Mit LINQ, und mit C# (ich weiß, VB nicht viel in diesen Tagen):

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

oder (kürzer und effizienter, aber wohl weniger klar):

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

Wenn Sie testen die Gleichheit, es lohnt sich, HashSet usw. zu betrachten, aber dies hilft nicht bei partiellen Übereinstimmungen, es sei denn, Sie teilen es in Fragmente auf und fügen eine Reihenfolge der Komplexität hinzu.

Update: Wenn Sie wirklich "StartsWith" meinen, dann könnten Sie die Liste sortieren und in ein Array platzieren; Verwenden Sie dann Array.BinarySearch, um jedes Element zu finden - prüfen Sie durch Nachschlagen, ob es sich um eine vollständige oder teilweise Übereinstimmung handelt.

Answer 2

Ich bin mir nicht sicher, ob es effizienter ist, aber Sie könnten über die Verwendung von Lambda Expressions denken.

Answer 3

Es gab eine Reihe von Vorschlägen aus einer früheren ähnlichen Frage "Best way to test for existing string against a large list of comparables".

Regex könnte für Ihre Anforderung ausreichend sein. Der Ausdruck wäre eine Verkettung aller Kandidaten-Teilstrings mit einem OR "-Operator" zwischen ihnen. Natürlich müssen Sie beim Erstellen des Ausdrucks auf nicht deklarierte Zeichen achten, oder Sie müssen es aufgrund von Komplexität oder Größenbeschränkungen nicht kompilieren.

Eine andere Möglichkeit wäre, eine trie data structure zu konstruieren, um alle Kandidaten-Teilstrings darzustellen (dies könnte etwas verdoppeln, was der Regex-Matcher macht). Wenn Sie jedes Zeichen in der Testzeichenfolge durchlaufen, erstellen Sie einen neuen Zeiger auf das Stammverzeichnis des Trie und erweitern vorhandene Zeiger auf das entsprechende Kind (falls vorhanden). Sie erhalten eine Übereinstimmung, wenn ein Zeiger ein Blatt erreicht.

Answer 4

Basierend auf Ihren Mustern wäre eine Verbesserung, wenn Sie StartsWith statt Contains verwenden. StartsWith muss nur jeden String durchlaufen, bis er den ersten Unterschied findet, anstatt die Suche an jeder Zeichenposition neu starten zu müssen, wenn sie einen findet.

Auch basierend auf Ihren Mustern sieht es so aus, als könnten Sie den ersten Teil des Pfades für myString extrahieren, dann den Vergleich rückgängig machen und nach dem Startpfad von myString in der String - Liste suchen andersherum.

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

return listOfStrings.Contains(startPath); 

EDIT: Das wäre noch schneller mit der HashSet Idee @Marc Gravell erwähnt, da Sie Contains-ContainsKey und die Lookup-O wäre ändern könnten (1) anstelle von O (N). Sie müssten sicherstellen, dass die Pfade genau übereinstimmen. Beachten Sie, dass dies keine allgemeine Lösung wie @Marc Gravell ist, sondern auf Ihre Beispiele zugeschnitten ist.

Entschuldigung für das C# -Beispiel. Ich hatte nicht genug Kaffee, um in VB zu übersetzen.

Answer 5

Wenn die Geschwindigkeit kritisch ist, sollten Sie nach dem Muster Aho-Corasick algorithm für Muster suchen.

Es ist ein trie mit Fehler-Links, dh Komplexität ist O (n + m + k), wobei n die Länge des Eingabetexts, m die kumulative Länge der Muster und k die Anzahl der Treffer ist. Sie müssen nur den Algorithmus ändern, um zu beenden, nachdem die erste Übereinstimmung gefunden wurde.

Answer 6

Haben Sie die Geschwindigkeit getestet?

d. H. Haben Sie einen Beispieldatensatz erstellt und profiliert? Es ist vielleicht nicht so schlimm wie du denkst.

Dies könnte auch etwas sein, das Sie in einen separaten Thread spawnen könnten und die Illusion von Geschwindigkeit geben!

Answer 7

myList.Any(myString.Contains); 

Answer 8

Ich mochte Marc 's Antwort, aber brauchte die enthält passend zu CaSe InSenSiTiVe. Diese

war die Lösung:

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

Answer 9

, wenn Sie bauen Ihr reiht es wie dieses

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