Performance Competition: Find least frequent number in a list

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if (list == null || list.Count == 0) { return null; } CountMap map = new CountMap(list.Count); for (int index = 0; index < list.Count; ++index) { // Only need to call increment here // The data structure is customized to initialize to 1 if not found // Reduces the amount of hashing required int current = list[index]; map.Increment(current); } int smallest = 0; int smallestVal = int.MaxValue; for (int index = 0; index < map.entries.Length; ++index) { var current = map.entries[index]; if (current.value < smallestVal) { // If we ever find a count of 1, it will be the minimum, so return here if (current.value == 1) { return current.key; } else if (current.value != 0) { smallest = current.key; smallestVal = current.value; } } } return smallest; } /// <summary> /// This is a stripped down version of the .NET Dictionary class optimized for this task. /// The .NET Dictionary code used was found here: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs /// This is not suitable for general usage. It cannot resize like a normal Dictionary, /// Nor can you modify or insert custom values - it only inserts 1 or increments. /// </summary> class CountMap { internal const Int32 HashPrime = 101; public static readonly int[] primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369}; public struct Entry { public int hashCode; public int next; public int key; public int value; } private IEqualityComparer<int> comparer; private int[] buckets; public Entry[] entries; private int count; public CountMap(int capacity) { Initialize(capacity); } public void Increment(int index) { int hashCode = comparer.GetHashCode(index) & 0x7FFFFFFF; int target = hashCode % buckets.Length; for (int i = buckets[target]; i >= 0; i = entries[i].next) { if (entries[i].hashCode == hashCode && entries[i].key == index) { ++entries[i].value; return; } } Add(index, 1, hashCode, target); } private void Add(int key, int value, int hashCode, int targetBucket) { int index = count; count++; entries[index].hashCode = hashCode; entries[index].next = buckets[targetBucket]; entries[index].key = key; entries[index].value = value; buckets[targetBucket] = index; } private void Initialize(int capacity) { int size = GetPrime(capacity); buckets = new int[size]; entries = new Entry[size]; for (int i = 0; i < buckets.Length; i++) { buckets[i] = -1; } comparer = EqualityComparer<int>.Default; } private static int GetPrime(int min) { for (int i = 0; i < primes.Length; i++) { int prime = primes[i]; if (prime >= min) return prime; } for (int i = (min | 1); i < Int32.MaxValue; i += 2) { if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i; } return min; } private static bool IsPrime(int candidate) { if ((candidate & 1) != 0) { int limit = (int)Math.Sqrt(candidate); for (int divisor = 3; divisor <= limit; divisor += 2) { if ((candidate % divisor) == 0) return false; } return true; } return (candidate == 2); } } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if (list != null && list.Any()) { var dict = new System.Collections.Concurrent.ConcurrentDictionary<int, int>(); Parallel.ForEach(list, i => dict.AddOrUpdate(i, 1, (key, oldValue) => oldValue + 1)); var min = dict.Values.Min(); return dict.First(pair => pair.Value == min).Key; } return null; } }

using System.Collections.Concurrent; public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if (list == null || !list.Any()) { return null; } var dictionary = new ConcurrentDictionary<int, int>(); Parallel.ForEach(list, item => { dictionary.AddOrUpdate(item, 1, (key, oldValue) => oldValue + 1); }); var minValue = dictionary.Values.Min(); return dictionary.First(t => t.Value == minValue).Key; } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if(list == null || list.Count <= 0) { return null; } var dict = new System.Collections.Concurrent.ConcurrentDictionary<int,int>(); System.Threading.Tasks.Parallel.ForEach(list, i => { dict.AddOrUpdate(i, 1, (k,v) => v += 1); }); return dict.OrderBy(c => c.Value).FirstOrDefault().Key; } }

using System.Collections.Generic; using System.Linq; public class Solution : ICodeRush { private readonly Dictionary<int, CountAndKey> _fDict = new Dictionary<int, CountAndKey>(); private class CountAndKey : IComparable<CountAndKey> { public int Repetitions; public int Key; public int CompareTo(CountAndKey other) { return Repetitions - other.Repetitions; } } public int? FindLeastFrequentNumber(IList<int> list) { // If list is null or empty, return null if (list == null || list.Count == 0) return null; // Build up a frequency dictionary _fDict.Clear(); foreach (var key in list) { CountAndKey value; if (_fDict.TryGetValue(key, out value)) { value.Repetitions++; } else { _fDict[key] = new CountAndKey { Key = key }; } } // Return the first instance of the minimum frequency dictionary key return _fDict.Values.Min().Key; } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { // return null for null or empty lists if (list == null || list.Count == 0) { return null; } Dictionary<int, int> found = new Dictionary<int, int>(list.Count / 4); for (int index = 0; index < list.Count; ++index) { // Two hashes per update - could be worse I guess int current = list[index]; int count; if (found.TryGetValue(current, out count)) { ++count; found[current] = count; } else { found.Add(current, 1); } } int smallest = 0; int smallestVal = int.MaxValue; // Pay the penalty once to make this a list; faster to iterate after var data = found.ToList(); for (int index = 0; index < data.Count; ++index) { var item = data[index]; if (item.Value < smallestVal) { // If we ever reach a 1, nothing will be lower, so just return this key now if (item.Value == 1) { return item.Key; } // If this is smaller than the least frequent so far, store the key and value else { smallest = item.Key; smallestVal = item.Value; } } } return smallest; } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if (list == null || list.Count == 0) return null; int b = list.Count; if (b < 3) return list[0]; if (b < 100) { int c = int.MaxValue, d = 0; for (int i = 0; i < b; i++) { int e = 0, f = list[i]; for (int j = i; j < b; j++) if (f == list[j]) e++; if (e == 1) return f; if (e < c) { c = e; d = f; } } } var a = new Dictionary<int, int>(); var g = new int[5000]; bool h = list == null, k = h; int l = g.Length, m = g[2666]; for (int i = 0; i < list.Count; i++) { int n = list[i]; if (n > -1 && n < 5000){ g[n]++; k = true; if (l > n) l = n; if (m < n) m = n + 1; } else { if (a.ContainsKey(n)) a[n]++; else a.Add(n, 1); h = true; } } int o = int.MaxValue, p = 0; if (k) { for (int i = l; i < m; i++) { if (g[i] < o) { o = g[i]; if (o == 1) return i; p = i; } } } if (h) { foreach (var q in a) { if (q.Value < o) { o = q.Value; if (o == 1) return q.Key; p = q.Key; } } } return p; } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if (list == null || list.Count == 0) { return null; } var lookup = new Dictionary<int, int>(); var array = list.ToArray(); int length = array.Length; int count = 0; while (count < length) { bool exists = lookup.ContainsKey(array[count]); switch (exists) { case true: lookup[array[count]]++; break; default: lookup.Add(array[count], 1); break; } count++; } int lowest = int.MaxValue; int key = 0; var lookupArray = lookup.ToArray(); int lookupLength = lookupArray.Length; int currentLookupIndex = 0; while (currentLookupIndex < lookupLength) { bool lower = lookupArray[currentLookupIndex].Value < lowest; switch(lower) { case true: lowest = lookupArray[currentLookupIndex].Value; key = lookupArray[currentLookupIndex].Key; break; default: break; } currentLookupIndex++; } return key; } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if(list == null || list.Count <= 0) { return null; } var dict = new Dictionary<int,int>(); int listVal = 0; for (int i = 0; i < list.Count; i++) { listVal = list[i]; if (!dict.ContainsKey(listVal)) { dict.Add(listVal,1); continue; } dict[listVal]++; } return dict.OrderBy(c => c.Value).FirstOrDefault().Key; } }

public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList<int> list) { if (list == null || list.Count == 0) return null; Dictionary<int, int> NumberCountDictionary = new Dictionary<int, int>(); foreach (int item in list) { if (!NumberCountDictionary.ContainsKey(item)) { NumberCountDictionary.Add(item, 1); } else { NumberCountDictionary[item]++; } } for (int i = 0; i < NumberCountDictionary.Count; i++) { if (NumberCountDictionary.ContainsValue(i)) { foreach (KeyValuePair<int, int> pair in NumberCountDictionary) { if (pair.Value == i) { return pair.Key; } } } } return null; } }