Iteration Rate and Data Type

Question

Does the iteration speed depend on the array (or list, linkedList, dictionary ect) on the data type?

Example: Array of 10 bools v / s array of 10 integers?

Answer 1

Yes, the data type matters. This has nothing to do with iteration; It has everything related to data types.

Value types

An int has a length of 4 bytes. A decimal is 16 bytes long. Thus, decimal is 4 times larger than int . Each time you retrieve a value from an array, that value is copied. In the case of decimal 16 bytes are copied. (In the case of a reference type, the link is copied, usually 4 or 8 bytes). Copying more bytes will simply slow down the iteration.

Boxing

If you iterate over a collection, there is a chance that you have a type of change. For example:

 foreach(object o in new int[] { 1,2,3 }) .... 

This will be each int attached to an object . It takes time. This has nothing to do with iteration; everything has to do with the fact that you are boxing.

Casting

Last example: There are also arrays in which you need to do the following:

 foreach(Person p in new object[] { ... }) .... 

Casting also takes extra time.

EDIT

Some temporary measurements to back up my requirement:

Answer 2

Run the code below if you want, but here's a quick comparison. All he does is iterate over the array / list and set the temporary variable to the value in this index.

Notice that somehow the performance of Int hit the start up success ... I don’t know why ... but it happens on repeated starts ...

  namespace Iterating_types { using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; class Program { static void Main(string[] args) { Thread.CurrentThread.Priority = ThreadPriority.Highest; Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime; Stopwatch watch = new Stopwatch(); int UPPER = 1000000; int[] int_arr = Enumerable.Range(1, UPPER).ToArray(); List<int> int_list = Enumerable.Range(1, UPPER).ToList(); Int32[] int32_arr = Enumerable.Range(1, UPPER).ToArray(); Int64[] int64_arr = new Int64[UPPER]; IntObject[] intobject_arr = new IntObject[UPPER]; List<IntObject> intobject_list = new List<IntObject>(); string[] string_arr = new string[UPPER]; List<string> string_list = new List<string>(); bool[] bool_arr = new bool[UPPER]; Boolean[] boolean_arr = new Boolean[UPPER]; List<bool> bool_list = new List<bool>(); List<Boolean> boolean_list = new List<Boolean>(); // Initializing some of the above for (int i = 0; i < UPPER; i++) { int64_arr[i] = (Int64) i; string_arr[i] = i.ToString(); string_list.Add(i.ToString()); intobject_arr[i] = new IntObject(i); intobject_list.Add(new IntObject(i)); bool_arr[i] = (i%2 ==0); boolean_arr[i] = (i%2 ==0); bool_arr[i] = (i%2 ==0); bool_list.Add(i%2 ==0); boolean_list.Add(i%2 == 0); } Console.WriteLine("Iterations: {0}{1}", UPPER, Environment.NewLine); Console.WriteLine("Thread priority: {0}", Thread.CurrentThread.Priority); Console.WriteLine("Process priority: {0}", Process.GetCurrentProcess().PriorityClass); Console.WriteLine("\n\rArrays:\t----------------------------------------------"); bool b; b = bool_arr[1]; watch.Start(); for (int i = 0; i < UPPER; i++) { b = bool_arr[i]; } watch.Stop(); Console.WriteLine("Type: bool\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); watch.Start(); for (int i = 0; i < UPPER; i++) { b = boolean_arr[i]; } watch.Stop(); Console.WriteLine("Type: Boolean\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); int temp_int; temp_int = int_arr[1]; watch.Start(); for (int i = 0; i < UPPER; i++) { temp_int = int_arr[i]; } watch.Stop(); Console.WriteLine("Type: Int\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); Int32 temp_int32 ; temp_int32 = int32_arr[1]; watch.Reset(); watch.Start(); for (int i = 0; i < UPPER; i++) { temp_int32 = int32_arr[i]; } watch.Stop(); Console.WriteLine("Type: Int32\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); Int64 temp_int64 ; temp_int64 = int64_arr[1]; watch.Reset(); watch.Start(); for (int i = 0; i < UPPER; i++) { temp_int64 = int64_arr[i]; } watch.Stop(); Console.WriteLine("Type: Int64\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); string s ; s = string_arr[1]; watch.Reset(); watch.Start(); for (int i = 0; i < UPPER; i++) { s = string_arr[i]; } watch.Stop(); Console.WriteLine("Type: string\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); temp_int = intobject_arr[1].IntValue; watch.Reset(); watch.Start(); for (int i = 0; i < UPPER; i++) { temp_int = intobject_arr[i].IntValue; } watch.Stop(); Console.WriteLine("Type: IntObject\tStructure: Array\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); Console.WriteLine("\n\rLists:\t----------------------------------------------"); watch.Reset(); watch.Start(); foreach (var val in bool_list) { b = val; } watch.Stop(); Console.WriteLine("Type: bool\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); watch.Reset(); watch.Start(); foreach (var val in boolean_list) { b = val; } watch.Stop(); Console.WriteLine("Type: Boolean\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); temp_int = int_list.First(); watch.Reset(); watch.Start(); foreach (var val in int_list) { temp_int = val; } watch.Stop(); Console.WriteLine("Type: Int\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); s = string_list.First(); watch.Reset(); watch.Start(); foreach (var val in string_list) { s = val; } watch.Stop(); Console.WriteLine("Type: string\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); temp_int = intobject_list.First().IntValue; watch.Reset(); watch.Start(); foreach (var val in intobject_list) { temp_int = val.IntValue; } watch.Stop(); Console.WriteLine("Type: IntObject\tStructure: List\t\tticks: {0}\tMiliSeconds:{1}", watch.ElapsedTicks, watch.ElapsedMilliseconds); Console.WriteLine(); Console.WriteLine("Hit any key to exit."); Console.ReadKey(); } } class IntObject { public int IntValue { get; set; } public IntObject () { IntValue = 0; } public IntObject(int i) { IntValue = i; } } } 

Answer 3

The simple answer is YES for reference types and NO for value types .

This is due to the fact that the implementation of generic .NET methods is performed in such a way that when using value types, boxing / unboxing is excluded, although not in ArrayLists. For example, a List<int> will store the integers of the array directly as integers on the heap, and not as objects. In the case of reference types, for example. List<string> , List<person> however, there will be a slight loss of time in converting / casting from an object to a data type.

See comparing HashSet and List with strings and objects .

Deciding which one to use between List , LinkedList , Dictionary , HashSet , etc., when you perform a large number of iterations, mainly depends on an understanding of how they are stored and their execution time complexity. The following is a list of the complexity of implementing and asymptotic indexing / iteration of some of the .NET Generics:

Internal implementation / asymptotic time complexity for .NET Generics

---

  + ------------------ + ------------------------------ --------- + ------------------------- + ------------- +
 |  |  |  Item [i] |  |
 |  Name |  Internal Implementation | ------------ + ------------ |  Iteration |
 |  |  |  Avg.  Case |  Worst Case |  |
 + ------------------ + ------------------------------ --------- + ------------ + ------------ + ------------- +
 |  List |  Array |  O (1) |  O (1) |  O (n) |
 |  LinkedList |  Doubly Linked List |  O (n) |  O (n) |  O (n) |
 |  Dictionary |  Hashtable with links to another array |  O (1) |  O (n) |  O (n) |
 |  Hashset |  Hashtable with links to another array |  O (1) |  O (n) |  O (n) |
 |  SortedDictionary |  Red-black tree |  O (log n) |  O (log n) |  O (n) |
 |  SortedList |  Array |  O (1) |  O (n) |  O (n) |
 |  SortedSet |  Red-black tree |  O (n) |  O (n) |  O (n) |
 + ------------------ + ------------------------------ --------- + ------------ + ------------ + ------------- + 

To summarize, we can determine the most likely rate of repetition of these data types based on their time complexity. Regarding the quick search of elements, List , SortedList , Dictionary and HashSet will always perform other actions, however List and SortedList not practical if you are going to process a large number of elements, which then put Dictionary and HashSet in advantage for large lists (where performance is greater Total).

Literature:

• Urgent Execution of the .NET Generic Collection
• Benchmarking List, HashSet, and SortedSet
• Time Difficulty Overview: Vocabulary Classes
• Shared Collections in C # - Time Difficulty Review
• Algorithms: Big-Oh Notation
• Sorted Dictionary (Tkey, Tvalue) - MSDN
• List (T) - MSDN

Glossary:

• Red ebony
• Boxing and Unboxing