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.