Sprawdź, czy ciąg zawiera element z listy (ciągów)

155

Dla następującego bloku kodu:

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

Wynik to:

Przypadek 1:

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

Przypadek 2:

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

Lista (listOfStrings) może zawierać kilka elementów (minimum 20) i należy ją porównać z tysiącami ciągów (np. MyString).

Czy istnieje lepszy (bardziej wydajny) sposób pisania tego kodu?

user57175
źródło

Odpowiedzi:

359

Z LINQ i używając C # (nie znam za dużo VB w dzisiejszych czasach):

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

lub (krótszy i wydajniejszy, ale prawdopodobnie mniej przejrzysty):

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

Gdybyś testował równość, warto przyjrzeć się temu HashSetitp., Ale to nie pomoże w przypadku częściowych dopasowań, chyba że podzielisz je na fragmenty i dodasz kolejność złożoności.


aktualizacja: jeśli naprawdę masz na myśli „StartsWith”, możesz posortować listę i umieścić ją w tablicy; następnie użyj, Array.BinarySearchaby znaleźć każdy element - sprawdź, sprawdzając, czy jest to pełne, czy częściowe dopasowanie.

Marc Gravell
źródło
1
Zamiast Contains użyłbym StartsWith na podstawie jego przykładów.
tvanfosson
@tvanfosson - to zależy od tego, czy przykłady są w pełni wyczerpujące, ale tak, zgadzam się. Oczywiście łatwo zmienić.
Marc Gravell
W jakim stopniu ten kod jest bardziej wydajny na poziomie algorytmicznym? Jest krótszy i szybszy, jeśli pętle w „Any” są szybsze, ale problem polegający na tym, że trzeba wielokrotnie wykonywać dokładne dopasowanie, jest taki sam.
Torsten Marek
Możesz ustawić komparator niestandardowy, jeśli używasz zestawu.
Fortyrunner
Drugi nie jest tak naprawdę bardziej efektywny z powodu jakiejkolwiek mierzalnej różnicy w praktyce.
ICR
7

kiedy konstruujesz swoje struny, powinno to wyglądać tak

bool inact = new string[] { "SUSPENDARE", "DIZOLVARE" }.Any(s=>stare.Contains(s));
Simi2525
źródło
5

Pojawiło się wiele sugestii z wcześniejszego podobnego pytania „ Najlepszy sposób na przetestowanie istniejącego ciągu na podstawie dużej listy elementów porównawczych ”.

Regex może być wystarczający dla twojego wymagania. Wyrażenie byłoby konkatenacją wszystkich podciągów kandydatów, z |operatorem OR pomiędzy nimi. Oczywiście podczas budowania wyrażenia musisz uważać na znaki bez znaku zmiany znaczenia lub na niepowodzenie jego kompilacji z powodu złożoności lub ograniczeń rozmiaru.

Innym sposobem na zrobienie tego byłoby skonstruowanie potrójnej struktury danych reprezentującej wszystkie kandydujące podciągi (może to w pewnym stopniu powielać to, co robi dopasowanie wyrażenia regularnego). Podczas przechodzenia przez każdy znak w ciągu testowym należy utworzyć nowy wskaźnik do korzenia trie i przesunąć istniejące wskaźniki do odpowiedniego elementu potomnego (jeśli istnieje). Dostajesz dopasowanie, gdy którykolwiek wskaźnik osiągnie liść.

Zach Scrivena
źródło
5

Podobała mi się odpowiedź Marca, ale potrzebowałem dopasowania Contains, aby było CaSe InSenSiTiVe.

To było rozwiązanie:

bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0))
WhoIsRich
źródło
Czy nie powinno być> -1?
wypisano
1
@CSharped Nie ma znaczenia, ponieważ> -1 (więcej niż minus 1) i> = 0 (więcej lub równe zero) to to samo.
WhoIsRich
2

Bazując na twoich wzorcach, jednym ulepszeniem byłoby przejście na używanie StartsWith zamiast Contains. StartsWith wymaga tylko iteracji przez każdy ciąg, aż znajdzie pierwszą niezgodność, zamiast ponownego uruchamiania wyszukiwania na każdej pozycji znaku, gdy ją znajdzie.

Ponadto na podstawie twoich wzorców wygląda na to, że możesz wyodrębnić pierwszą część ścieżki dla myString, a następnie odwrócić porównanie - szukając początkowej ścieżki myString na liście ciągów zamiast na odwrót.

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

return listOfStrings.Contains( startPath );

EDYCJA : Byłoby to jeszcze szybsze przy użyciu idei HashSet, o której wspomina @Marc Gravell, ponieważ można by zmienić Containsna, ContainsKeya wyszukiwanie byłoby O (1) zamiast O (N). Musiałbyś upewnić się, że ścieżki dokładnie pasują. Zwróć uwagę, że nie jest to ogólne rozwiązanie, jak @Marc Gravell, ale jest dostosowane do twoich przykładów.

Przepraszamy za przykład w C #. Nie mam dość kawy, żeby przetłumaczyć na VB.

tvanfosson
źródło
Ponownie zaczyna się od; może posortuj wstępnie i użyj wyszukiwania binarnego? To może być znowu szybsze.
Marc Gravell
2

Stare pytanie. Ale od VB.NETtego czasu był pierwotny wymóg. Używając tych samych wartości zaakceptowanej odpowiedzi:

listOfStrings.Any(Function(s) myString.Contains(s))
Luis Lavieri
źródło
1

Czy przetestowałeś prędkość?

tj. Czy utworzyłeś przykładowy zestaw danych i sprofilowałeś go? Może nie być tak źle, jak myślisz.

Może to być również coś, co możesz odrodzić w osobnym wątku i dać iluzję prędkości!

Fortyrunner
źródło
0

Jeśli szybkość ma kluczowe znaczenie, możesz poszukać algorytmu Aho-Corasick dla zestawów wzorców.

Jest to trie z łączami niepowodzenia, to znaczy złożoność wynosi O (n + m + k), gdzie n to długość tekstu wejściowego, m łączna długość wzorców, ik liczba dopasowań. Musisz tylko zmodyfikować algorytm, aby zakończył działanie po znalezieniu pierwszego dopasowania.

Torsten Marek
źródło
0
myList.Any(myString.Contains);
WIRN
źródło
0

Wadą Containsmetody jest to, że nie pozwala na określenie typu porównania, co jest często ważne przy porównywaniu ciągów. Zawsze uwzględnia kulturę i wielkość liter. Myślę więc, że odpowiedź WhoIsRich jest cenna, chcę tylko pokazać prostszą alternatywę:

listOfStrings.Any(s => s.Equals(myString, StringComparison.OrdinalIgnoreCase))
Al Kepp
źródło