Increase performance of string matching function I've benchmarked my program, and have discovered that the single function taking the most time is the one that does the following.


Takes string that is a delimited list, and splits it into individual strings (Within the program, the individual strings are called statements)
Looks at the individual strings, compares them to a known set of strings (Called a statement library. It contains additional information relating to these strings that I need)


I cannot change the input data, since it comes from several different systems, and the closest thing we can get to something in common is a delimited list of strings.

So, enough background, the first implementation of this was a naive set of LINQ statements:

var statements = textStatements
    .Select(ts =&gt; Library.Statements
        .FirstOrDefault(s =&gt; ts.Equals(s.FullText, StringComparison.OrdinalIgnoreCase)))
    .Where(s =&gt; s != null).ToList();


So, statements is a list of Statement objects, which contain the additional data I need. I figure this is worst case is about O(n^2)-ish.

Once this function was identified as a bottleneck, I made a first attempt at optimizing this function. First, I ensured the split list of statements, and the known list of statements were both sorted, and then implemented this:

var textStatements = SplitStatements(data).ToList();
var statementCount = textStatements.Count;
var libraryCount = Library.Statements.Count;
var libraryOffset = 0;
var foundStatements = new Dictionary&lt;string, Statement&gt;();
for (var i = 0; i &lt; statementCount; i++)
{
    var thisStatement = textStatements[i];
    for (var j = libraryOffset; j &lt; libraryCount; j++)
    {
        var currentLibraryStatement = Library.Statements[j];
        if (string.Equals(thisStatement, currentLibraryStatement.FullText, StringComparison.OrdinalIgnoreCase))
        {
            foundStatements[(currentLibraryStatement.Category.Name + currentLibraryStatement.Code).ToUpperInvariant()] = currentLibraryStatement;
            libraryOffset = j + 1;
            break;
        }
        if (string.Compare(thisStatement, currentLibraryStatement.FullText, StringComparison.OrdinalIgnoreCase) &lt; 0)
        {
            libraryOffset = j;
            break;
        }
    }
}


Essentially, I loop through the statements I need to look up, and start working through the library of statements, remembering where the last statement was found, so I can exclude all statements in the library that are before the last one found.

This did result in a speedup, but not as much as I would hope, hence me throwing this out here to see if I can get another perspective.
You're just looking to find any textStatement's that exist in Library.Statements? A HashSet will make easy work of this:

IEnumerable&lt;string&gt; splitInputStatements = SplitStatements(data);
HashSet&lt;string&gt; inputStatements = new HashSet&lt;string&gt;(splitInputStatements);

// If you're using Library.Statements in this way many times, it might just
// be a good idea to keep all of them cached in a HashSet to begin with so
// you don't have to build this.
IEnumerable&lt;string&gt; libraryStatementTexts = Library.Statements.Select(s =&gt; s.FullText);
HashSet&lt;string&gt; libraryStatements = new HashSet&lt;string&gt;(libraryStatementTexts);

// That's it, this is your result:
var matches = inputStatements.Intersect(libraryStatements);


This site has some handy notes for when to use collections of certain types.

Alternatively, you can skip making inputStatements a HashSet and continue using the IEnumerable directly like so::

inputStatements.Where(is =&gt; libraryStatements.Contains(is));