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 => Library.Statements        .FirstOrDefault(s => ts.Equals(s.FullText, StringComparison.OrdinalIgnoreCase)))    .Where(s => 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<string, Statement>();for (var i = 0; i < statementCount; i++){    var thisStatement = textStatements[i];    for (var j = libraryOffset; j < 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) < 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.
Increase performance of string matching function
c#;strings