For the following block of code:
For I = 0 To listOfStrings.Count - 1
If myString.Contains(lstOfStrings.Item(I)) Then
Return True
End If
Next
Return False
The output is:
Case 1:
myString: C:\Files\myfile.doc
listOfString: C:\Files\, C:\Files2\
Result: True
Case 2:
myString: C:\Files3\myfile.doc
listOfString: C:\Files\, C:\Files2\
Result: False
The list (listOfStrings) may contain several items (minimum 20) and it has to be checked against a thousands of strings (like myString).
Is there a better (more efficient) way to write this code?
This question is related to
c#
vb.net
list
coding-style
performance
myList.Any(myString.Contains);
There were a number of suggestions from an earlier similar question "Best way to test for existing string against a large list of comparables".
Regex might be sufficient for your requirement. The expression would be a concatenation of all the candidate substrings, with an OR "|
" operator between them. Of course, you'll have to watch out for unescaped characters when building the expression, or a failure to compile it because of complexity or size limitations.
Another way to do this would be to construct a trie data structure to represent all the candidate substrings (this may somewhat duplicate what the regex matcher is doing). As you step through each character in the test string, you would create a new pointer to the root of the trie, and advance existing pointers to the appropriate child (if any). You get a match when any pointer reaches a leaf.
As I needed to check if there are items from a list in a (long) string, I ended up with this one:
listOfStrings.Any(x => myString.ToUpper().Contains(x.ToUpper()));
Or in vb.net:
listOfStrings.Any(Function(x) myString.ToUpper().Contains(x.ToUpper()))
If speed is critical, you might want to look for the Aho-Corasick algorithm for sets of patterns.
It's a trie with failure links, that is, complexity is O(n+m+k), where n is the length of the input text, m the cumulative length of the patterns and k the number of matches. You just have to modify the algorithm to terminate after the first match is found.
Have you tested the speed?
i.e. Have you created a sample set of data and profiled it? It may not be as bad as you think.
This might also be something you could spawn off into a separate thread and give the illusion of speed!
myList.Any(myString.Contains);
when you construct yours strings it should be like this
bool inact = new string[] { "SUSPENDARE", "DIZOLVARE" }.Any(s=>stare.Contains(s));
The drawback of Contains
method is that it doesn't allow to specify comparison type which is often important when comparing strings. It is always culture-sensitive and case-sensitive. So I think the answer of WhoIsRich is valuable, I just want to show a simpler alternative:
listOfStrings.Any(s => s.Equals(myString, StringComparison.OrdinalIgnoreCase))
Have you tested the speed?
i.e. Have you created a sample set of data and profiled it? It may not be as bad as you think.
This might also be something you could spawn off into a separate thread and give the illusion of speed!
Based on your patterns one improvement would be to change to using StartsWith instead of Contains. StartsWith need only iterate through each string until it finds the first mismatch instead of having to restart the search at every character position when it finds one.
Also, based on your patterns, it looks like you may be able to extract the first part of the path for myString, then reverse the comparison -- looking for the starting path of myString in the list of strings rather than the other way around.
string[] pathComponents = myString.Split( Path.DirectorySeparatorChar );
string startPath = pathComponents[0] + Path.DirectorySeparatorChar;
return listOfStrings.Contains( startPath );
EDIT: This would be even faster using the HashSet idea @Marc Gravell mentions since you could change Contains
to ContainsKey
and the lookup would be O(1) instead of O(N). You would have to make sure that the paths match exactly. Note that this is not a general solution as is @Marc Gravell's but is tailored to your examples.
Sorry for the C# example. I haven't had enough coffee to translate to VB.
There were a number of suggestions from an earlier similar question "Best way to test for existing string against a large list of comparables".
Regex might be sufficient for your requirement. The expression would be a concatenation of all the candidate substrings, with an OR "|
" operator between them. Of course, you'll have to watch out for unescaped characters when building the expression, or a failure to compile it because of complexity or size limitations.
Another way to do this would be to construct a trie data structure to represent all the candidate substrings (this may somewhat duplicate what the regex matcher is doing). As you step through each character in the test string, you would create a new pointer to the root of the trie, and advance existing pointers to the appropriate child (if any). You get a match when any pointer reaches a leaf.
Based on your patterns one improvement would be to change to using StartsWith instead of Contains. StartsWith need only iterate through each string until it finds the first mismatch instead of having to restart the search at every character position when it finds one.
Also, based on your patterns, it looks like you may be able to extract the first part of the path for myString, then reverse the comparison -- looking for the starting path of myString in the list of strings rather than the other way around.
string[] pathComponents = myString.Split( Path.DirectorySeparatorChar );
string startPath = pathComponents[0] + Path.DirectorySeparatorChar;
return listOfStrings.Contains( startPath );
EDIT: This would be even faster using the HashSet idea @Marc Gravell mentions since you could change Contains
to ContainsKey
and the lookup would be O(1) instead of O(N). You would have to make sure that the paths match exactly. Note that this is not a general solution as is @Marc Gravell's but is tailored to your examples.
Sorry for the C# example. I haven't had enough coffee to translate to VB.
Have you tested the speed?
i.e. Have you created a sample set of data and profiled it? It may not be as bad as you think.
This might also be something you could spawn off into a separate thread and give the illusion of speed!
There were a number of suggestions from an earlier similar question "Best way to test for existing string against a large list of comparables".
Regex might be sufficient for your requirement. The expression would be a concatenation of all the candidate substrings, with an OR "|
" operator between them. Of course, you'll have to watch out for unescaped characters when building the expression, or a failure to compile it because of complexity or size limitations.
Another way to do this would be to construct a trie data structure to represent all the candidate substrings (this may somewhat duplicate what the regex matcher is doing). As you step through each character in the test string, you would create a new pointer to the root of the trie, and advance existing pointers to the appropriate child (if any). You get a match when any pointer reaches a leaf.
If speed is critical, you might want to look for the Aho-Corasick algorithm for sets of patterns.
It's a trie with failure links, that is, complexity is O(n+m+k), where n is the length of the input text, m the cumulative length of the patterns and k the number of matches. You just have to modify the algorithm to terminate after the first match is found.
Old question. But since VB.NET
was the original requirement. Using the same values of the accepted answer:
listOfStrings.Any(Function(s) myString.Contains(s))
The drawback of Contains
method is that it doesn't allow to specify comparison type which is often important when comparing strings. It is always culture-sensitive and case-sensitive. So I think the answer of WhoIsRich is valuable, I just want to show a simpler alternative:
listOfStrings.Any(s => s.Equals(myString, StringComparison.OrdinalIgnoreCase))
when you construct yours strings it should be like this
bool inact = new string[] { "SUSPENDARE", "DIZOLVARE" }.Any(s=>stare.Contains(s));
Based on your patterns one improvement would be to change to using StartsWith instead of Contains. StartsWith need only iterate through each string until it finds the first mismatch instead of having to restart the search at every character position when it finds one.
Also, based on your patterns, it looks like you may be able to extract the first part of the path for myString, then reverse the comparison -- looking for the starting path of myString in the list of strings rather than the other way around.
string[] pathComponents = myString.Split( Path.DirectorySeparatorChar );
string startPath = pathComponents[0] + Path.DirectorySeparatorChar;
return listOfStrings.Contains( startPath );
EDIT: This would be even faster using the HashSet idea @Marc Gravell mentions since you could change Contains
to ContainsKey
and the lookup would be O(1) instead of O(N). You would have to make sure that the paths match exactly. Note that this is not a general solution as is @Marc Gravell's but is tailored to your examples.
Sorry for the C# example. I haven't had enough coffee to translate to VB.
I liked Marc's answer, but needed the Contains matching to be CaSe InSenSiTiVe.
This was the solution:
bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0))
There were a number of suggestions from an earlier similar question "Best way to test for existing string against a large list of comparables".
Regex might be sufficient for your requirement. The expression would be a concatenation of all the candidate substrings, with an OR "|
" operator between them. Of course, you'll have to watch out for unescaped characters when building the expression, or a failure to compile it because of complexity or size limitations.
Another way to do this would be to construct a trie data structure to represent all the candidate substrings (this may somewhat duplicate what the regex matcher is doing). As you step through each character in the test string, you would create a new pointer to the root of the trie, and advance existing pointers to the appropriate child (if any). You get a match when any pointer reaches a leaf.
Old question. But since VB.NET
was the original requirement. Using the same values of the accepted answer:
listOfStrings.Any(Function(s) myString.Contains(s))
Have you tested the speed?
i.e. Have you created a sample set of data and profiled it? It may not be as bad as you think.
This might also be something you could spawn off into a separate thread and give the illusion of speed!
I liked Marc's answer, but needed the Contains matching to be CaSe InSenSiTiVe.
This was the solution:
bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0))
As I needed to check if there are items from a list in a (long) string, I ended up with this one:
listOfStrings.Any(x => myString.ToUpper().Contains(x.ToUpper()));
Or in vb.net:
listOfStrings.Any(Function(x) myString.ToUpper().Contains(x.ToUpper()))
If speed is critical, you might want to look for the Aho-Corasick algorithm for sets of patterns.
It's a trie with failure links, that is, complexity is O(n+m+k), where n is the length of the input text, m the cumulative length of the patterns and k the number of matches. You just have to modify the algorithm to terminate after the first match is found.
Source: Stackoverflow.com