Überprüfen Sie, ob eine Zeichenfolge ein Element aus einer Liste (von Zeichenfolgen) enthält.

154

Für den folgenden Codeblock:

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

Die Ausgabe 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 enthalten (mindestens 20) und muss mit Tausenden von Zeichenfolgen (wie myString) verglichen werden.

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

user57175
quelle

Antworten:

358

Mit LINQ und C # (ich kenne VB heutzutage nicht viel):

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 die Gleichheit testen, lohnt es sich, sich HashSetusw. anzuschauen, aber dies hilft bei Teilübereinstimmungen nur, wenn Sie es in Fragmente aufteilen und eine Reihenfolge der Komplexität hinzufügen.


Update: Wenn Sie wirklich "StartsWith" meinen, können Sie die Liste sortieren und in ein Array einfügen. Verwenden Sie dann Array.BinarySearch, um jedes Element zu finden. Überprüfen Sie anhand der Suche, ob es sich um eine vollständige oder teilweise Übereinstimmung handelt.

Marc Gravell
quelle
1
Anstelle von Contains würde ich StartsWith basierend auf seinen Beispielen verwenden.
Tvanfosson
@tvanfosson - das hängt davon ab, ob die Beispiele vollständig enthalten sind, aber ja, ich würde zustimmen. Natürlich einfach zu ändern.
Marc Gravell
Inwieweit ist dieser Code auf algorithmischer Ebene effizienter? Es ist kürzer und schneller, wenn die Schleifen in "Any" schneller sind, aber das Problem, dass Sie viele Male genau übereinstimmen müssen, ist das gleiche.
Torsten Marek
Sie können einen benutzerdefinierten Komparator einrichten, wenn Sie einen Satz verwenden.
Fortyrunner
Der zweite ist durch messbare Unterschiede in der Praxis nicht wirklich effizienter.
ICR
7

Wenn Sie Ihre Zeichenfolgen erstellen, sollte dies so sein

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

Es gab eine Reihe von Vorschlägen aus einer früheren ähnlichen Frage " Bester Weg, um vorhandene Zeichenfolgen anhand einer großen Liste von Vergleichsdaten zu testen ".

Regex könnte für Ihre Anforderung ausreichen. Der Ausdruck wäre eine Verkettung aller in Frage kommenden Teilzeichenfolgen mit einem ODER- |Operator dazwischen. Natürlich müssen Sie beim Erstellen des Ausdrucks auf nicht entflohene Zeichen achten oder auf einen Fehler beim Kompilieren aufgrund von Komplexität oder Größenbeschränkungen.

Eine andere Möglichkeit, dies zu tun, besteht darin, eine Trie-Datenstruktur zu erstellen , die alle Kandidaten-Teilzeichenfolgen darstellt (dies kann etwas duplizieren, was der Regex-Matcher tut). Wenn Sie durch jedes Zeichen in der Testzeichenfolge gehen, erstellen Sie einen neuen Zeiger auf die Wurzel des Versuchs und erweitern vorhandene Zeiger auf das entsprechende untergeordnete Element (falls vorhanden). Sie erhalten eine Übereinstimmung, wenn ein Zeiger ein Blatt erreicht.

Zach Scrivena
quelle
4

Ich mochte Marc's Antwort, brauchte aber das Contains Matching, um CaSe InSenSiTiVe zu sein.

Dies war die Lösung:

bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0))
WhoIsRich
quelle
Sollte es nicht> -1 sein?
CSharped
1
@CSharped spielt keine Rolle, da> -1 (mehr als minus 1) und> = 0 (mehr oder gleich Null) dasselbe sind.
WhoIsRich
2

Basierend auf Ihren Mustern besteht eine Verbesserung darin, StartsWith anstelle von Contains zu verwenden. StartsWith muss nur jede Zeichenfolge durchlaufen, bis die erste Nichtübereinstimmung gefunden wird, anstatt die Suche an jeder Zeichenposition neu starten zu müssen, wenn eine gefunden wird.

Basierend auf Ihren Mustern können Sie möglicherweise den ersten Teil des Pfads für myString extrahieren und dann den Vergleich umkehren. Suchen Sie in der Liste der Zeichenfolgen nach dem Startpfad von myString und nicht umgekehrt.

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 ändern könnten Containszu ContainsKeyund die Suche wäre O (1) anstelle von O (N). Sie müssten sicherstellen, dass die Pfade genau übereinstimmen. Beachten Sie, dass dies keine allgemeine Lösung ist, wie dies bei @Marc Gravell der Fall ist, sondern auf Ihre Beispiele zugeschnitten ist.

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

Tvanfosson
quelle
Re beginnt mit; vielleicht vorsortieren und binäre Suche verwenden? Das könnte wieder schneller sein.
Marc Gravell
2

Alte Frage. Aber da VB.NETwar die ursprüngliche Anforderung. Verwenden Sie die gleichen Werte der akzeptierten Antwort:

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

Hast du die Geschwindigkeit getestet?

dh Haben Sie einen Beispieldatensatz erstellt und ein Profil erstellt? Es kann nicht so schlimm sein, wie Sie denken.

Dies könnte auch etwas sein, das Sie in einem separaten Thread hervorbringen und die Illusion von Geschwindigkeit vermitteln könnten!

Fortyrunner
quelle
0

Wenn die Geschwindigkeit kritisch ist, sollten Sie nach dem Aho-Corasick-Algorithmus für Mustersätze suchen .

Es ist ein Versuch mit Fehlerverknüpfungen, dh die Komplexität ist O (n + m + k), wobei n die Länge des Eingabetextes, m die kumulative Länge der Muster und k die Anzahl der Übereinstimmungen ist. Sie müssen nur den Algorithmus ändern, um ihn zu beenden, nachdem die erste Übereinstimmung gefunden wurde.

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

Der Nachteil der ContainsMethode besteht darin, dass kein Vergleichstyp angegeben werden kann, was beim Vergleichen von Zeichenfolgen häufig wichtig ist. Es ist immer kultursensitiv und case sensitive. Ich denke, die Antwort von WhoIsRich ist wertvoll. Ich möchte nur eine einfachere Alternative zeigen:

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