3
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ If I understand correctly. You can store all your library statement words in a dictionary and look them up. \$\endgroup\$
    – hocho
    Apr 25, 2014 at 19:33
  • \$\begingroup\$ @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...) \$\endgroup\$ Apr 25, 2014 at 19:54
  • \$\begingroup\$ 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) \$\endgroup\$
    – MrSmith42
    Apr 25, 2014 at 20:21

3 Answers 3

1
\$\begingroup\$

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));
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.