Algorithmic complexity of hashset iteration in C #
Investigating Reflector 's insides of the .NET framework classes, you can often find out a lot of curious things. For example, once (quite a long time ago) I learned that for a QuickSort, it is very easy to come up with a class of input data that will be sorted in quadratic time. So, on “pyramid” arrays (that is, on those in which the maximum element is in the middle, the second and third largest - to the left and right of it, and so on), the quick sort was comparable in time to the bubble one. The reason is obvious - the middle element of the array was chosen as the median. I don’t know how this problem is now, but if it still takes place, it deserves a separate post.
Speech is about another. Everyone who is familiar with the dotnet, I believe, is known for the System.Collections.Generic class . HashSet <T> . According to MSDN, the HashSet class provides high-performance set operations. How do you think, in what time will your computer, say, two hundred times run through a hashset of one element? A hundredth of a second? Less? It is not a fact!
The fact is that the internal device of a hashset is such that instead of deleted elements there can appear “holes” - elements marked in a special way that the iterator runs in any case. Thus, if, for example, first putting a million elements in a hashset, and then removing almost all of it, leaving only a few, then the time spent on iterating over these remaining elements would be much longer than the time that would show a run of a comparable hashset which was not performed delete operations.
')
The following code demonstrates how an iteration time for a hashset without a difficult past may differ from an iteration time for a life-honored hashset, in which a million elements were first thrown, and then almost all were taken:
On my machine it displays this:
As you can see, the time difference is huge - many thousands of times, although functionally we did the same action in both cases - we ran on a set of one element.
Strictly speaking, the time complexity of the iteration over all elements of the Dashnet HashSet is at worst not O (N), where N is the number of elements in it, but O (the maximum number of elements in the hashset that it has ever had).
So, friends, the conclusion is simple. Read MSDN with disbelief, use the .NET classes with care, open this framework with Reflector and love each other. Then there will be a performance.
Speech is about another. Everyone who is familiar with the dotnet, I believe, is known for the System.Collections.Generic class . HashSet <T> . According to MSDN, the HashSet class provides high-performance set operations. How do you think, in what time will your computer, say, two hundred times run through a hashset of one element? A hundredth of a second? Less? It is not a fact!
The fact is that the internal device of a hashset is such that instead of deleted elements there can appear “holes” - elements marked in a special way that the iterator runs in any case. Thus, if, for example, first putting a million elements in a hashset, and then removing almost all of it, leaving only a few, then the time spent on iterating over these remaining elements would be much longer than the time that would show a run of a comparable hashset which was not performed delete operations.
')
The following code demonstrates how an iteration time for a hashset without a difficult past may differ from an iteration time for a life-honored hashset, in which a million elements were first thrown, and then almost all were taken:
using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .
using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .using System; using System.Collections. Generic ; using System.Diagnostics; public class HashSetIterationPerformance { public const int MaxItemsCount = 10000000; public const int RepeatIterations = 200; public static TimeSpan MeasureIterationTime(HashSet< int > hashSet) { var stopwatch = new Stopwatch(); stopwatch.Start(); for ( int i = 0; i < RepeatIterations; ++i) foreach ( var x in hashSet) { // Do nothing } return new TimeSpan (stopwatch.Elapsed.Ticks / RepeatIterations); } public static void Main( string [] args) { var hashSet = new HashSet< int >(); hashSet.Add(0); Console .WriteLine( "Usual scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); hashSet = new HashSet< int >(); // - : [0..MaxItemsCount) for ( int i = 0; i < MaxItemsCount; ++i) { hashSet.Add(i); } // , for ( int i = 1; i < MaxItemsCount; ++i) { hashSet.Remove(i); } Console .WriteLine( "Add/Remove scenario. Iteration time: {0}" , MeasureIterationTime(hashSet)); } } * This source code was highlighted with Source Code Highlighter .
On my machine it displays this:
Usual scenario. Iteration time: 00:00:00.0000032
Add/Remove scenario. Iteration time: 00:00:00.0468619
As you can see, the time difference is huge - many thousands of times, although functionally we did the same action in both cases - we ran on a set of one element.
Strictly speaking, the time complexity of the iteration over all elements of the Dashnet HashSet is at worst not O (N), where N is the number of elements in it, but O (the maximum number of elements in the hashset that it has ever had).
So, friends, the conclusion is simple. Read MSDN with disbelief, use the .NET classes with care, open this framework with Reflector and love each other. Then there will be a performance.
Source: https://habr.com/ru/post/90217/
All Articles