c# - Improving performance of Dictionary using Arrays -

consider counting number of occurrences of particular letter in word.

i came solution.

string = "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 solution can improved further using arrays better using above dictionary.

i guess, dictionary lookup o(1) (arrays o(1), correct ?) . ideas how re-write program using arrays performs better?

arrays o(1), correct

arrays o(1) when accessing known offset. o(n) when have scan array find particular match.

you not out-perform dictionary type of operation in general case.

you can leverage accessing known offset caveat use arrays limited case. example, if know have input in range 'a'..'z', can have array of counts

int[] counts = new int[26];  // initialize array elements 0 first. count[(int)(ch - 'a')]++; 

this type of code fragile in change range of input values breaks it. performance gain not matter vs. dictionary cases. if think case needs small performance edge, benchmark before using more fragile implementation arrays.

this type of operation pretty common. wrote generic class 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]     {                  {             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 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 0 , increment         }         else         {             counts[key]+=amount;         }     }      public void decrement(t key, int amount = 1)     {         if (!counts.containskey(key))         {             counts.add(key, -amount); // initialize 0 , decrement         }         else         {             counts[key]-=amount;         }     }       /// <summary>     /// not correctly implement ienumerable on .net (seems compile on mono).  should 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;     }  }