Some Coding Optimizations

Recently i found some interesting coding challenges in some of our solutions developed in C# , when looking at the code we found that the developers got some kind of crazy staff ding just the product with any idea over performance kind of this snippet of code :

Icollection<T> myCollection = new Collection<T>(input.Distinct().ToList())

Whats the problem ? yes you are solving your problem just by adding performance problem.

Lets look at the Cyclomatic Complecity of this line of code.

First : ToList() , this is an extension method of IEnumerable<T> , the problem is that you are using a method which internally uses the Array , so it iterates over all elements one by one , so we have a O(n) comlplexity.

Second: Distinct() The ditinct method also is an extension method of IEnumerable<T> with internally uses a Set<T> and iterates over elements as bellow:

Set<TSource> set = new Set<TSource>(comparer); foreach (TSource element in source) if (set.Add(element)) yield return element;

so we have another O(n) complexity for this one , till now we are over 2N that it looks like OK, we are at O(n).

Third: The Collection uses IList<T> internally , and in initialization there is no cost , but when going to lookup you got a worst case ok O(n)

Finally : Where analysis found worst situation possible.

myObjectList.ForEach(item=> { if(myCollection.Any(el => el.Id == item.Id){ // Doing Some Staff } });

So iterating N times for each item of M times , So the result was O(n*m) Complexity.

So the Complexity of the solution will be O(n + N*m) = O(n+n²) = O(n²)

Result :

How we can simply optimize theses 5 lines of code,

HashSet<T> mySet = new HashSet<T>(ranked); myObjectList.ForEach(item=> { if(mySet.TryGetValue(item.Id, out int resultId){ // Doing Some Staff } });

The result will have a complexity of O(n), let’s have a deep look at the calculation

The HashSet Initialization is O(n) as it iterates over the elements in the list and keep unique values. Just Your T object need to implement the Comparer and HashCode methods

The ForEach iterates over the object list , the TryGetValue results at O(1) and the Foreach part as O(n) so there is a O(1) * O(n) = O(n) complexity

The complete solution has O(n) + O(n) = O(2n) = O(n)

Note: As we calculate the complexity we remove all constants.

Using tools , libraries and frameworks can help us to gain the time , but using them in a wrong way is the worst.

Originally published at https://www.linkedin.com.