Take the 2-minute tour ×

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)

  foreach (Staff stf in staff)
    if (staffMatchesSearch(stf))


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

share|improve this question
do you really want to toString those ints? Seems like you'd want a matches string method and matches int method... I mean, if I'm in center 13, I shouldn't show up because someone searches for center 1 or center 3... –  corsiKa Nov 16 '11 at 3:56
Try implementing one of the Boyer-Moore family of string searching algorithms? Preprocessing either the search term, or the Staff objects and reusing the result could save a lot of time. –  millimoose Nov 16 '11 at 3:57
Do your really want to search for all the matches for each of the staff properties each time? As a user, I would want to only search on one or two known fields at a time. –  ChandlerPelhams Nov 16 '11 at 3:57
@glowcoder This is exactly the behaviour they are looking for. –  Ozzah Nov 16 '11 at 4:01
Can you wait until maybe two letters are entered before searching, or only do a search if they enter an asterisk? –  Daryl Nov 16 '11 at 4:01
show 3 more comments

5 Answers

up vote 7 down vote accepted

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.

share|improve this answer
"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" This will only work if they type additional characters at the end. It is a special-case optimization. Might be worth doing, but it won't speed up all operations, and could make logic more complicated for other operations. –  Merlyn Morgan-Graham Nov 16 '11 at 4:13
@MerlynMorgan-Graham fair point but this special case is probably the most common case so probably worth the code complexity –  Robert Levy Nov 16 '11 at 4:15
Perhaps also: Check the key pressed - if its NaN then don't check the int properties. –  BlueChippy Nov 16 '11 at 4:16
@BlueChippy - nice. i marked this answer as a wiki so feel free to add that to the list –  Robert Levy Nov 16 '11 at 4:19
Thanks @RobertLevy also wondering: ToLower() all the properties that you are searching on, and also ToLower all input strings on keypress. Then the search must always be case insensitive (as all are lower). –  BlueChippy Nov 16 '11 at 4:54
add comment

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.

share|improve this answer
this reduction in Contains calls will have negligible benefits (the one big call is doing just as much work as the smaller ones) –  Robert Levy Nov 16 '11 at 4:18
Yes the changes to Contains() wouldn't be a huge difference, I think the main benefit of this approach would be removing the need to keep on calling ToLower() each time. –  mikel Nov 16 '11 at 4:22
The issue is, I have deliberately split it up into multiple small ifs so that in the best-case scenario it will bail out with a return true quickly. If I add all the possible search terms together in a (string1 + string2 + ... + stringN).ToLower().Contains() then I have to concatenate, process, and search through a much longer string. I think this would run slower (???). –  Ozzah Nov 16 '11 at 4:29
I ran a bunch of tests and found that your method, on average, will give results in about 75-85ms whereas my method takes about 136ms on average. I am going to combine this with the pre-evaluated ToLower() and see how that goes! –  Ozzah Nov 16 '11 at 5:16
It shaved another 20ms off. With the pre-evaluated lower-case strings, it only takes about 60ms on average, which is quite good! –  Ozzah Nov 16 '11 at 5:25
show 1 more comment

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


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.

share|improve this answer
add comment

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;


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

Here is an MSDN link, discussing fast string comparisons.

share|improve this answer
This is a really good idea and I'll definitely use it in future, but for this instance I think it's obsolete since I'm now pre-computing the lower-case versions. Thanks :) –  Ozzah Nov 16 '11 at 21:40
Seems reasonable, although you should check out this question about upper vs lower case: stackoverflow.com/questions/9033/hidden-features-of-c#12137 –  Joel Rondeau Nov 16 '11 at 22:00
add comment
using System;
using System.Text.RegularExpressions;
namespace PatternMatching1
    class Program
        static void Main(string[] args)
                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();


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


share|improve this answer
add comment

Your Answer


