Frequency Distribution (Code Challenge)
- Page Owner: Not Set
- Last Reviewed: 2019-08-23
Frequency Distribution
Create a function that returns the frequency distribution of an array. This function should return an object, where the keys are the unique elements and the values are the frequency in which those elements occur.
Examples
getFrequencies(["A", "B", "A", "A", "A"]) ➞ { A: 4, B: 1 }
getFrequencies([1, 2, 3, 3, 2]) ➞ { "1": 1, "2": 2, "3": 2 }
getFrequencies([true, false, true, false, false]) ➞ { true: 2, false: 3 }
getFrequencies([]) ➞ {}
Notes
- If given an empty array, return an empty object (see example #4).
- The object should be in the same order as in the input array.
Tests
getFrequencies(['A', 'A']), {A: 2}
getFrequencies(['A', 'B', 'A', 'A', 'A']), {A: 4, B: 1}
getFrequencies(['A', 'B', 'C', 'A', 'A']), {A: 3, B: 1, C: 1}
getFrequencies([true, false, true, false, false]), {'true': 2, 'false': 3}
getFrequencies([1, 2, 3, 3, 2]), {'1': 1, '2': 2, '3': 2}
getFrequencies([]), {}
Answer
I did the opposite of code-golf. Forgive me.
public class Distribution<T>
{
public Distribution(T value, int frequency)
{
Value = value;
Frequency = frequency;
}
public T Value { get; }
public int Frequency { get; private set; }
public void Add() { Frequency += 1; }
}
public delegate IList<Distribution<T>> GetDistribution<T>(IEnumerable<T> list);
public class FrequencyDistributionUtility
{
private static ConcurrentDictionary<Type, object> definedFunctions = new ConcurrentDictionary<Type, object>();
public static IEnumerable<Distribution<T>> GetDistribution<T>(IEnumerable<T> list)
{
var method = (GetDistribution<T>)definedFunctions.GetOrAdd(typeof(T), (_) => CreateGetDistributionFunction<T>());
return method(list);
}
public static Distribution<T> FindMatch<T>(List<Distribution<T>> list, T value)
{
var result = list.Find(x => x.Value.Equals(value));
return result;
}
public static GetDistribution<T> CreateGetDistributionFunction<T>()
{
// Dynamically create the GetDistribution method for some reason
var type = typeof(T);
DynamicMethod method = new DynamicMethod($"GET_DIST_{type.Name}", typeof(IList<Distribution<T>>), new[] { typeof(IEnumerable<T>) });
var gen = method.GetILGenerator();
// var results = new List<Distribution<T>>();
var results = gen.DeclareLocal(typeof(List<Distribution<T>>));
gen.Emit(OpCodes.Newobj, typeof(List<Distribution<T>>).GetConstructor(new Type[0]));
gen.Emit(OpCodes.Stloc, results);
// var enumerator = list.GetEnumerator();
var enumerator = gen.DeclareLocal(typeof(IEnumerator<T>));
gen.Emit(OpCodes.Ldarg, 0);
gen.Emit(OpCodes.Callvirt, typeof(IEnumerable<T>).GetMethod("GetEnumerator"));
gen.Emit(OpCodes.Stloc, enumerator);
var whileLoop = gen.DefineLabel();
var whileLoopEnd = gen.DefineLabel();
gen.MarkLabel(whileLoop);
// do {
{
// if (!enumerator.MoveNext()) { break; }
gen.Emit(OpCodes.Ldloc, enumerator); // [enumerator]
gen.Emit(OpCodes.Dup); // [enumerator|enumerator] // Saving a local here!
gen.Emit(OpCodes.Callvirt, typeof(System.Collections.IEnumerator).GetMethod("MoveNext")); //[enumerator|moveNext?]
gen.Emit(OpCodes.Brfalse, whileLoopEnd); // [enumerator]
// var value = enumerator.Current;
var value = gen.DeclareLocal(typeof(T));
gen.Emit(OpCodes.Callvirt, typeof(IEnumerator<T>).GetProperty("Current").GetGetMethod()); // [value]
gen.Emit(OpCodes.Stloc, value);
// var matchingItem = FrequencyDistributionFunctionFactory.FindMatch(results, value);
gen.Emit(OpCodes.Ldloc, results);
gen.Emit(OpCodes.Ldloc, value);
gen.Emit(OpCodes.Call, typeof(FrequencyDistributionUtility).GetMethod("FindMatch").MakeGenericMethod(typeof(T)));
gen.Emit(OpCodes.Dup); // Put matchingItem twice on the stack: [matchingItem | matchingItem], save str/ld calls
var isNull = gen.DefineLabel();
var endNullCheck = gen.DefineLabel();
// if (matchingItem != null) {
gen.Emit(OpCodes.Brfalse, isNull); // Pop matchingItem and see if it's null [matchingItem]
{
// matchingItem.Add();
gen.Emit(OpCodes.Callvirt, typeof(Distribution<T>).GetMethod("Add"));
gen.Emit(OpCodes.Br, endNullCheck);
} // else
gen.MarkLabel(isNull);
{
gen.Emit(OpCodes.Pop); // Pop dupe matchingItem off the stack []
// results.Add(new Distribution<T>(value, 1));
gen.Emit(OpCodes.Ldloc, results);
gen.Emit(OpCodes.Ldloc, value);
gen.Emit(OpCodes.Ldc_I4, 1);
gen.Emit(OpCodes.Newobj, typeof(Distribution<T>).GetConstructor(new[] { typeof(T), typeof(int) }));
gen.Emit(OpCodes.Callvirt, typeof(List<Distribution<T>>).GetMethod("Add", new[] { typeof(Distribution<T>) }));
}
gen.MarkLabel(endNullCheck);
}
gen.Emit(OpCodes.Br, whileLoop);
// } // while
gen.MarkLabel(whileLoopEnd); // [enumerator]
gen.Emit(OpCodes.Pop); // []
gen.Emit(OpCodes.Ldloc, results);
gen.Emit(OpCodes.Ret);
return (GetDistribution<T>)method.CreateDelegate(typeof(GetDistribution<T>));
}
}
Comments
- -1. No structs.
Additional Posts
In C#, it would be:
public List<KeyValuePair<object, int>> GetFrequencies(params object[] values)
{
return values
.GroupBy(v => v)
.Select(v => new KeyValuePair<object, int>(v.Key, v.Count()))
.ToList();
}
### Comments
- Tidy, but does this satisfy the "The object should be in the same order as in the input array" requirement? AFAIK, a `Dictionary` does not guarantee order.
- @BobDavidson Edited.
- Well, it's confusing -- how can it be in the same "order" when we're distilling multiple values down to a single value? The above code will put it in the same order as _the first appearance_ of each key. @JohnPavek ?
- That's how I'm interpreting it. The test answers also have the same issue, as JS doesn't guarantee the order of plain objects either.
This is my tentative answer, but i think theres a way to shorten it:
from collections import Counter as c
def getFrequencies(li):
for i,j in zip(c(li).keys(),c(li).values()):
print(i,j)
getFrequencies(['A', 'A'])
getFrequencies(['A', 'B', 'A', 'A', 'A'])
getFrequencies(['A', 'B', 'C', 'A', 'A'])
getFrequencies([True, False, True, False, False])
getFrequencies([1, 2, 3, 3, 2])
getFrequencies([])
Another JS golfing for me. Only 52 characters.
f=x=>x.reduce((a,c)=>{a[c]=(a[c]||0)+1;return a},{})
Here is my code golfed attempt. Johns playing some better game than me and my python skills:
from collections import Counter as B
def f(l):
A=B()
for C in l:A[C]+=1
print(A)