Improving performance of Dictionary using Arrays

Question

Consider counting number of occurrences of a particular letter in a word.

I came up with this solution.

string a = "aabbcdc"; //Output: a:2,b:2,c:2,d:1
var dict = new Dictionary<char, int>();
foreach(var @char in a)
{
  if(dict.ContainsKey(@char)) 
    dict[@char] = dict[@char] + 1; 
  else dict.Add(@char, 1);
}
foreach(var keyValuePair in dict)
  Console.WriteLine("Letter = {0}, Value = {1}", keyValuePair.Key, keyValuePair.Value);

My friend argued that this solution can be improved further using Arrays as they are better than using the above Dictionary.

I guess, Dictionary lookup is O(1) (arrays also O(1), correct ?) . Any ideas how to re-write the program using arrays which performs better?

Answer 1

If you are sure the letters are all within the ASCII range, i.e. 0-255, you can use an array and access it by the char value.

var arr = new int[256];     //Make sure it's initialized to 0
foreach(var @char in a)
{
    arr[(int)@char] ++;
}

Answer 2

arrays also O(1), correct

Arrays are only O(1) when accessing a known offset. They are O(n) when you have to scan the array to find a particular match.

You will not out-perform a Dictionary for this type of operation in the general case.

You can leverage the accessing a known offset caveat to use arrays for this limited case. For example, if you know that you will only have input in the range 'a'..'z', you can have an array of counts

int[] counts = new int[26];

// Initialize all array elements to 0 first.
count[(int)(ch - 'a')]++;

This type of code is fragile in that a change to the range of input values breaks it. Any performance gain will not matter vs. Dictionary for almost all cases. If you think your case really needs that small performance edge, benchmark before using the more fragile implementation with arrays.

This type of operation is pretty common. I wrote a generic class for it

[Serializable]
public class OccurrenceCounter<T>
{
    private Dictionary<T, int> counts;

    public OccurrenceCounter()
    {
        Initialize(default(StreamingContext));
    }

    [OnDeserialized]
    public void Initialize(StreamingContext context)
    {
        if (counts == null)
        {
            counts = new Dictionary<T, int>();
            counts.OnDeserialization(this);
        }
    }

    public int this[T key]
    {
        get 
        {
            if (counts.ContainsKey(key))
            {
                return counts[key];
            }
            else return 0;
        }
    }

    public bool ContainsKey(T key)
    {
        return counts.ContainsKey(key);
    }

    public int Total()
    {
        return counts.Sum(c => c.Value);
    }

    public int Count()
    {
        return counts.Count;
    }

    public int TotalFor(IEnumerable<T> keys)
    {
        if (keys == null) throw new ArgumentException("Parameter keys must not be null.");

        HashSet<T> hash = keys.ToHashSet();
        return counts.Where(k => hash.Contains(k.Key)).Sum(k => k.Value);
    }


    public void Increment(T key, int amount = 1)
    {
        if (!counts.ContainsKey(key))
        {
            counts.Add(key, amount); // Initialize to zero and increment
        }
        else
        {
            counts[key]+=amount;
        }
    }

    public void Decrement(T key, int amount = 1)
    {
        if (!counts.ContainsKey(key))
        {
            counts.Add(key, -amount); // Initialize to zero and decrement
        }
        else
        {
            counts[key]-=amount;
        }
    }


    /// <summary>
    /// Could not correctly implement IEnumerable on .NET (seems to compile on Mono).  Should be fixed.
    /// See: http://stackoverflow.com/questions/16270722/ienumerablet-int-arity-and-generic-type-definitions
    /// </summary>
    /// <returns></returns>
    public IEnumerable<KeyValuePair<T, int>> Iterate()
    {
        foreach (KeyValuePair<T, int> kvp in counts) yield return kvp;
    }

}