High-speed string matching in C#

Question

I have a list of about 10,000 staff members in a List<T> and I have a ListBox which contains a subset of those staff, depending on the search term in a text box.

Say a Staff object has the following publicly exposed properties:

string FirstName
string LastName
string MiddleName
   int StaffID
   int CostCentre

I could write a function like this:

bool staffMatchesSearch(Staff stf)
{
  if (tbSrch.Text.Trim() == string.Empty)
    return true; // No search = match always.

  string s = tbSrch.Text.Trim().ToLower();

  // Do the checks in the order most likely to return soonest:
  if (stf.LastName.ToLower().Contains(s))
    return true;
  if (stf.FirstName.ToLower().Contains(s))
    return true;
  if (stf.MiddleName.ToLower().Contains(s))
    return true;

  if (stf.CostCentre.ToString().Contains(s))
    return true; // Yes, we want partial matches on CostCentre
  if (stf.StaffID.ToString().Contains(s))
    return true; // And also on StaffID

  return false;
}

and then do something like:

tbSrch_TextChanged(object sender, EventArgs e)
{
  lbStaff.BeginUpdate();
  lbStaff.Items.Clear();

  foreach (Staff stf in staff)
    if (staffMatchesSearch(stf))
      lbStaff.Items.Add(stf);

  lbStaff.EndUpdate();
}

The filtering is re-evaluated every time the user changes the contents of the tbSrch box.

This works, and it's not awfully slow, but I was wondering if I could make it any faster?

I have tried to re-write the whole thing to be multi-threaded, however with only 10,000 staff members the overhead seemed to take away the bulk of the benefit. Also, there were a bunch of other bugs like if searching for "John", the user first presses "J" which spools up the threads, but when the user presses the "o" another set are spooled up before the first lot have had a chance to return their results. A lot of the time, the results get returned in a jumbled order and all sorts of nasty things happen.

I can think of a few tweaks that would make the best-case scenario significantly better, but they would also make the worst-case scenario a lot worse.

Do you have any ideas on how this can be improved?

---

Great suggestions I've implemented far, and their results:

• Add a delay on the ValueChanged event so that if the user types a 5-character name quickly on the keyboard, it only performs 1 search at the end rather than 5 in series.
• Pre-evaluate ToLower() and store in the Staff class (as a [NonSerialized] attribute so it doesn't take up extra space in the save file).
• Add a get property in Staff which returns all the search criteria as a single, long, lower-case, concatenated string. Then run a single Contains() on that. (This string is stored in the Staff object so it only gets constructed once.)

So far, these have lowered search times from around 140ms to about 60ms (though these numbers are highly subjective depending on the actual search performed and number of results returned).

Answer 1

1) as pointed out in the comments, you probably shouldn't .ToString the numeric fields - just match the numbers

2) the ToLower calls are a perf drain. Add lowercased versions of these properties to the Staff class so the ToLower only has to be done once

3) when the user enters another character, you don't need to reevaluate all items. entering a character will only reduce the number of matches so only reevaluate the previous matches.

4) use a timer to introduce a delay between when the user types and when you kick off a search. if they are typing multiple characters quickly, you might as well wait until they've paused for half a second

5) Check the key pressed. If NaN then don't check the int properties.

Answer 2

You could add a 'SearchTerm' private property to the Staff object that's (FirstName + LastName + MiddleName + StaffID + CostCentre).ToLower() , and do the Contains() check on that instead. This would stop you having to do a ToLower() on each string each time and reduce the number of Contains() checks from 5 to 1.

Answer 3

You could try implementing a trie or "prefix-tree":

http://en.wikipedia.org/wiki/Trie

This would allow you to search for text that begins with the value.

I believe the linked article on suffix-trees would allow you to do a full text search, though it has higher storage requirements.

Make sure you ToLower all your data when inserting it into your structure so you don't have to do case insensitive comparisons while doing your lookup.

Answer 4

In seeing what you've done (mostly from comments on @mikel's answer), it sounds like you're getting there. One suggestion I haven't seen which could offer a speed increase is to do a comparison using StringComparison.OrdinalIgnoreCase. In your case, it would mean replacing

if (stf.LastName.ToLower().Contains(s))
  return true;

with

if (stf.LastName.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0)
  return true;

Here is an MSDN link, discussing fast string comparisons.

Answer 5

using System;
using System.Text.RegularExpressions;
namespace PatternMatching1
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Console.WriteLine("Please enter the first string.");
                string str = Console.ReadLine(); ;
                string replacestr = Regex.Replace(str, "[^a-zA-Z0-9_]+", " ");



                Console.WriteLine("Please enter the second string.");
                string str1 = Console.ReadLine(); ;
                string replacestr1 = Regex.Replace(str1, "[^a-zA-Z0-9_]+", " ");



                if (replacestr.Length == replacestr1.Length)
                {
                    char[] cFirst = replacestr.ToLower().ToCharArray();
                    char[] cSecond = replacestr1.ToLower().ToCharArray();

                    Array.Sort<char>(cFirst);
                    Array.Sort<char>(cSecond);

                    if ((new string(cFirst)).Equals((new string(cSecond))))
                        Console.WriteLine("Both String Same");
                    else
                        Console.WriteLine("Both String Not Same");
                }
                else
                    Console.WriteLine("oopsss, something going wrong !!!! try again");
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
            Console.Read();
        }
    }
}

`