How to optimize this validation method?

Question

Looking to optimize this method so it will run quicker, but can't seem to find anything. WOrking in .NET 3.5. ExcludedWords and NewCodes are both HashSet of strings.

    private bool isValid(String code)
    {
        String pattern = "[a-zA-Z]{3}";

        if (chkLessThan2Letters.Checked && Regex.IsMatch(code, pattern))
        {
            return false;
        }

        foreach (string s in excludedWords)
        {
            if (code.Contains(s))
            {
                return false;
            }
        }

        if (newCodes.Contains(code))
        {
            return false;
        }

        return true;
    }

Answer 1

Before you optimize this, make sure that it actually needs optimization and that you're not wasting your time. Have you checked that this is a performance bottleneck in your application?

One way to optimize this is to store your excluded words in a datastructure like a Trie. This will let you see if some word in in the trie potentially faster than iterating through a list.

Answer 2

Assuming this is really your bottleneck, a few options:

1. Create your Regex ahead of time and precompile it.

2. If excludedWords doesn't change while you're running, try creating a long OR Regex, like (badWord1|badWord2|xyz) and precompiling it. This should create a fairly efficient search-tree that will be faster than performing a repeated Contains call.

Answer 3

This could help:

    private static readonly Regex matchCode = new Regex("[a-zA-Z]{3}", RegexOptions.Compiled);

    private bool IsValid(string code)
    {
        if (this.chkLessThan2Letters.Checked && matchCode.IsMatch(code))
        {
            return false;
        }

        if (this.excludedWords.Any(code.Contains))
        {
            return false;
        }

        return !this.newCodes.Contains(code);
    }

Answer 4

I was going to make this a comment to Dan's answer, but it started getting quite long (and I wanted to try and actually code it to see if I remembered how).

Assuming excludedWords is big and doesn't change between builds of the application (or if it does you have the ability to replace a single dll), you should build a dll containing the compiled regex representing it to get a much better search then you would if you used that linq expression.

using System.Collections.Generic;
using System.Reflection;
using System.Reflection.Emit;
using System.Text;
using System.Text.RegularExpressions;

namespace RegexLibAssemblyBuilder 
{
    public class RegexCompilationTest 
    {
        public static IEnumerable<string> ExcludedWords() {...}

        public static void Main() 
        {
            //build pattern
            var excludedWordsRegex = new StringBuilder();
            bool first = true;

            foreach (var word in ExcludedWords()) 
            {
                if (!first) 
                {
                    excludedWordsRegex.Append("|");
                }
                excludedWordsRegex.Append(Regex.Escape(word));
                first = false;
            }

            // Define regular expression here
            var expr = new RegexCompilationInfo(excludedWordsRegex.ToString(),
                RegexOptions.None,
                "ExcludedWordsRegex",
                "Utilities.RegularExpressions",
                true);

            //add other assembly attributes you want just like this
            ConstructorInfo ctor = typeof(System.Reflection.AssemblyTitleAttribute).GetConstructor(new[] { typeof(string) });
            CustomAttributeBuilder[] attBuilder = { new CustomAttributeBuilder(ctor, new object[] { "General-purpose library of compiled regular expressions" }) };

            Regex.CompileToAssembly(new[] { expr }, new AssemblyName("RegexLib, Version=1.0.0.1001, Culture=neutral, PublicKeyToken=null"), attBuilder);
        }
    }
}

Then in code you could use it like this (after linking your project to this new assembly):

private static readonly Regex excludedWords= new ExcludedWordsRegex();

private bool IsValid(string code)
{
    if (this.chkLessThan2Letters.Checked && matchCode.IsMatch(code))
    {
        return false;
    }

    if (excludedWords.IsMatch(code))
    {
        return false;
    }
...

Answer 5

I am basing my answer on Jesse's. It would be unwise to throw away some of his optimizations. The only improvement I can offer is not using Regex but doing the equivalent check manually, because it is such a simple regex. If you have to use a different one, then this will not work. Note that I also made the methods static, made them take every parameter explicitly, thus making this code more "functional". Also, it looks less like Java because method starts with a capital letter and I use string instead of String. You are probably storing stuff as a HashSet but I am taking Collection as an input. Firstly, I was not sure which exact container you have. Secondly, this should not affect the speed, but if you prefer to do it differently, then you may do so.

    // using System.Linq;
    private static bool IsValidCode(string code, bool checkLessThanTwoLetters, ICollection<string> excludedWords, ICollection<string> newCodes)
    {
        // TODO: The naming is confusing but all I did was re-factored the code.
        if (checkLessThanTwoLetters && ContainsThreeLetterCode(code: code))
        {
            return false;
        }

        if (excludedWords.Any(code.Contains))
        {
            return false;
        }

        return !newCodes.Contains(code);
    }

    // I updated this method thanks to a comment by Bill.
    private static bool ContainsThreeLetterCode(string code)
    {
        if (code == null || code.Length != 3)
        {
            return false;
        }

        int ctr = 0;
        foreach(char ch in code)
        {
            ctr = Char.IsLetter(ch) ? ctr + 1 : 0;
            if (ctr == 3)
            {
                return true;
            }
        }

        return false;
    }