# 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 => 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.

• If I understand correctly. You can store all your library statement words in a dictionary and look them up. – hocho Apr 25 '14 at 19:33
• @hocho, I have absolutely no clue why I didn't think of that. I made that change, and the exclusive time for that function fell through the floor. Make it an answer, and I'll accept it (The new function on top of the list is a constructor that does nothing but set properties...) – Matt Sieker Apr 25 '14 at 19:54
• You can also store the library word in a map with a hash value as a key to reduce the look up time in the library to about O(1) – MrSmith42 Apr 25 '14 at 20:21

You're just looking to find any textStatement's that exist in Library.Statements? A HashSet will make easy work of this:

IEnumerable<string> splitInputStatements = SplitStatements(data);
HashSet<string> inputStatements = new HashSet<string>(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<string> libraryStatementTexts = Library.Statements.Select(s => s.FullText);
HashSet<string> libraryStatements = new HashSet<string>(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 => libraryStatements.Contains(is));


If I understand correctly. You can store all your library statement words in a dictionary and look them up.