Increase performance of string matching function

Question

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.

Answer 1

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));

Answer 2

An option you can use if you want to optimize your code is to sort both arrays before running through your loop. You would have two indexes (libraryIndex and statementsIndex) and for each iteration of your loop at least one of the two will move forward. This results in a O(N + M) instead of O(N * M) complexity (where N is the count of statements and M the count of statements in the library).

Sorting using List.Sort() method takes O(n Log n). All in all the overall complexity ends up being O(n Log n) with n being the largest count between your library and the input statements.

Also, just for code review, don't use 'var', explicit the types (for clarity).

That would give you the follwing :

List<string> textStatements = SplitStatements(data).ToList();
textStatements.Sort(); //Check comparison options to ignore case
Library.Statements.Sort(); //Is it legal in your application ? Else copy the list and sort the copy.
int statementCount = textStatements.Count;
int libraryCount = Library.Statements.Count;
int statementIndex = 0;
int libraryIndex = 0;
Dictionary<string, Statement> found = new Dictionary<string, Statement>();

while (statementIndex < statementCount && libraryIndex < libraryCount)
{
    string thisStatement = textStatements[statementIndex];
    string currentLibraryStatement = Library.Statements[libraryIndex].FullText;

    int compareResult = string.Compare(thisStatement, currentLibraryStatement, StringComparison.OrdinalIgnoreCase);

    if (compareResult == 0)
    {
        //We found a statement
        found[(currentLibraryStatement.Category.Name + currentLibraryStatement.Code).ToUpperInvariant()] = currentLibraryStatement;
        //We can increase both our indexes
        libraryIndex++;
        statementIndex++;
    }
    else if (compareResult < 0)
    {
        //CurrentStatement preceeds CurrentLibraryStatement, 
        //so the statement is not in the library (else it would have been found already)
        //We increase our statementIndex
        statementIndex++;
    }
    else
    {
        //CurrentStatement follows CurrentLibraryStatement
        //So we increase only the libraryIndex
        libraryIndex++;
    }
}

Note that your library could be already sorted before calling your method, that way it is only sorted once and the complexity depends only on the number of statements you have as input. If the sorting occurs during the data collection it could be even faster.

Note also that this only works if there are no doubles in your lists.

Answer 3

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