Piter's Home Page

It is time to say Happy New Year and Merry Christmas for everyone! I hope that upcoming year will be even better than previous and it will bring only positive emotions.

For me, personally next year puts a lot of outstanding challenges and great tasks. And I truly hope that I will manage to solve at least half of them.

New Year is a family holiday and it is a great pleasure for me to meet 2009 with my family. It is snowy and cold in Kiev today and this day remind me my childhood. I would like to thank my parents my sister and my brother that I could remember only warmest and sweatiest moments from New Year celebrations in the past, when I was a child. 

I wish a good health, brightest thoughts and good luck in a new year to all my family, my closest friends and you my reader. See You in next year!

P.S. This Year I had 22267 unique visitors on my WebSite which is almost 5 times greater than a year before. I whish the progress will remain the same next year!

Lets assume we have an array of objects and we want to find duplicate values inside it. From the first glance the task seems trivial. But what if there is more then billion items inside this array. Will it be possible to find those values in a reasonable amount of time.

Further thinking reveals that there are a lot of options to implement this algorithm. Starting from the most simple double pass O(N^2), to more sophisticated O(n*Log(n)) and even more improved n*k where k is a number of possible different objects inside an array.

This picture above shows benchmark of 6 different algorithms which solves this problem:

I’ve tested them on the following CPU:

You may download detailed results together with C# implementations of these algorithms by the following links: Results, Source + Bin

This excercise showed that standard collections in .NET are very efficient. It is worth to mention that algorithms based on HashSet<> and Dictionary<,> are among fastest. However it would be very nice to see so efficient implementations of at least Balanced Binary Tree structure in the future versions of .NET Framework.

Ура заработало