title: High-speed string matching in C#
body: <p>I have a list of about 10,000 staff members in a <code>List&lt;T&gt;</code> and I have a <code>ListBox</code> which contains a subset of those staff, depending on the search term in a text box.</p>
  
  <p>Say a <code>Staff</code> object has the following publicly exposed properties:</p>
  
  <pre><code>string FirstName
  string LastName
  string MiddleName
     int StaffID
     int CostCentre
  </code></pre>
  
  <p>I could write a function like this:</p>
  
  <pre><code>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;
  }
  </code></pre>
  
  <p>and then do something like:</p>
  
  <pre><code>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();
  }
  </code></pre>
  
  <p>The filtering is re-evaluated every time the user changes the contents of the <code>tbSrch</code> box.</p>
  
  <p>This works, and it's not <em>awfully</em> slow, but I was wondering if I could make it any faster?</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Do you have any ideas on how this can be improved?</p>
  
  <hr>
  
  <p><b>Great suggestions I've implemented far, and their results:</b></p>
  
  <ul>
  <li>Add a delay on the <code>ValueChanged</code> 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.</li>
  <li>Pre-evaluate <code>ToLower()</code> and store in the <code>Staff</code> class (as a <code>[NonSerialized]</code> attribute so it doesn't take up extra space in the save file).</li>
  <li>Add a <code>get</code> property in <code>Staff</code> which returns all the search criteria as a single, long, lower-case, concatenated string. Then run a single <code>Contains()</code> on that. (This string is stored in the <code>Staff</code> object so it only gets constructed once.)</li>
  </ul>
  
  <p>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).</p>