High performance "contains" search in list of strings in C#

c# string search sorting contains
njr101 picture njr101 · Sep 29, 2011 · Viewed 18.8k times · Source

I have a list of approx. 500,000 strings, each approx. 100 characters long. Given a search term, I want to identify all strings in the list that contain the search term. At the moment I am doing this with a plain old dataset using the Select method ("MATCH %term%"). This takes about 600ms on my laptop. I'd like to make it faster, maybe 100-200ms.

What would be a recommended approach?

Performance is critical so I can trade memory footprint for better performance if necessary (within reason). The list of strings will not change once initialised so calculating hashes would also be an option.

Does anyone have a recommendation and which C# data structures are best suited to the task?

Answer

StriplingWarrior picture StriplingWarrior · Sep 29, 2011

I've heard good things about Lucene.NET when it comes to performing quick full-text searches. They've done the work to figure out the fastest data structures and such to use. I'd suggest giving that a shot.

Otherwise, you might just try something like this:

var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();

But it probably won't get you down to 100ms.

Related questions

Using C# to check if string contains a string in string array

I want to use C# to check if a string value contains a word in a string array. For example, string stringToCheck = "text1text2text3"; string[] stringArray = { "text1", "someothertext", etc... }; if(stringToCheck.contains stringArray) //one of the items? { } How can …

Read More
Look at each character in a string

I was wondering if anyone knew how to look through a string at each character and then add each character to a new string? Just a really really basic example, I can add the ToUpper and ToLower validation and such.

Read More
How can C#'s string.IndexOf perform so fast, 10 times faster than ordinary for loop find?

I have a very long string (60MB in size) in which I need to find how many pairs of '<' and '>' are in there. I have first tried my own way: char pre = '!'; …

Read More