C# Array or Dictionary?
Solution 1
The best choice depends on how you need to access the elements.
If you want to access them by index, then use an Array. Arrays in C# have constant access speed, and are very similar to a C++ array in terms of speed for access.
Dictionaries, however, have very fast access (the Item property approaches O(1) access time, but depends on how good of an implementation the stored key has for GetHashCode). If you need to lookup your items based on a key value and not by index, then dictionary would be appropriate instead.
Solution 2
Yes, if you know the index the speed is constant O(1), much like a lookup in a hashtable backed dictionary (e.g. Dictionary<>).
If the index is not known then you will have to perform a search (linear if the items are unsorted O(n) or binary if they are O(log n)).
That said, in real terms the array lookup will be quicker because a hashtable lookup is two operations: calculate the hash of the key to get an index and retrieve the value from an internal array at that index.
Also note that a if the hashcode of the key is badly implemented, the hashtable's magical properties quickly evaporate and, in the worst case (where every key has the same hashcode) you will end up with an elaborate linked-list in which every look up will be a linear search at a cost of O(n). Double check those hashcodes!
Solution 3
It depends on the way you are going to get elements from the array. If you are going to get elements by positions (index) in the array then array will be quicker (or at least not slower than dictionary). If you are going to search for elements in the array than dictionary will be faster.
Solution 4
An update on the last post... the code now includes a class for the list data structure. I've removed some bugs from the code. It should deliver the right results now.
It seems that for one dimensional data structures, a list structure can actually be faster that an array. But for two dimensional structures, as in the code below, arrays are substantially faster than lists, and significantly faster than dictionaries.
But it all depends on what you want to use the data structures for. For relatively small data sets, dictionaries and lists are often more convenient structures to use.
public interface IDataStructureTimeTestHandler
{
void PerformTimeTestsForDataStructures();
}
public class DataStructureTimeTestHandler : IDataStructureTimeTestHandler
{
// Example of use:
//IDataStructureTimeTestHandler iDataStructureTimeTestHandler = new DataStructureTimeTestHandler();
//iDataStructureTimeTestHandler.PerformTimeTestsForDataStructures();
private IDataStructureTimeTest[] iDataStructureTimeTests;
private TimeSpan[,] testsResults;
public DataStructureTimeTestHandler()
{
iDataStructureTimeTests = new IDataStructureTimeTest[3];
testsResults = new TimeSpan[4, 3];
}
public void PerformTimeTestsForDataStructures()
{
iDataStructureTimeTests[0] = new ArrayTimeTest();
iDataStructureTimeTests[1] = new DictionaryTimeTest();
iDataStructureTimeTests[2] = new ListTimeTest();
for (int i = 0; i < iDataStructureTimeTests.Count(); i++)
{
testsResults[0, i] = iDataStructureTimeTests[i].InstantiationTime();
testsResults[1, i] = iDataStructureTimeTests[i].WriteTime();
testsResults[2, i] = iDataStructureTimeTests[i].ReadTime(LoopType.For);
testsResults[3, i] = iDataStructureTimeTests[i].ReadTime(LoopType.Foreach);
}
}
}
public enum LoopType
{
For,
Foreach
}
public interface IDataStructureTimeTest
{
TimeSpan InstantiationTime();
TimeSpan WriteTime();
TimeSpan ReadTime(LoopType loopType);
}
public abstract class DataStructureTimeTest
{
protected IStopwatchType iStopwatchType;
protected long numberOfElements;
protected int number;
protected delegate void TimeTestDelegate();
protected DataStructureTimeTest()
{
iStopwatchType = new StopwatchType();
numberOfElements = 10000000;
}
protected void TimeTestDelegateMethod(TimeTestDelegate timeTestMethod)
{
iStopwatchType.StartTimeTest();
timeTestMethod();
iStopwatchType.EndTimeTest();
}
}
public class ArrayTimeTest : DataStructureTimeTest, IDataStructureTimeTest
{
private int[,] integerArray;
public TimeSpan InstantiationTime()
{
TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_));
return iStopwatchType.TimeElapsed;
}
private void InstantiationTime_()
{
integerArray = new int[numberOfElements, 2];
}
public TimeSpan WriteTime()
{
TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_));
return iStopwatchType.TimeElapsed;
}
private void WriteTime_()
{
number = 0;
for (int i = 0; i < numberOfElements; i++)
{
integerArray[i, 0] = number;
integerArray[i, 1] = number;
number++;
}
}
public TimeSpan ReadTime(LoopType dataStructureLoopType)
{
switch (dataStructureLoopType)
{
case LoopType.For:
ReadTimeFor();
break;
case LoopType.Foreach:
ReadTimeForEach();
break;
}
return iStopwatchType.TimeElapsed;
}
private void ReadTimeFor()
{
TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_));
}
private void ReadTimeFor_()
{
for (int i = 0; i < numberOfElements; i++)
{
number = integerArray[i, 1];
}
}
private void ReadTimeForEach()
{
TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_));
}
private void ReadTimeForEach_()
{
foreach (int i in integerArray)
{
number = i;
}
}
}
public class DictionaryTimeTest : DataStructureTimeTest, IDataStructureTimeTest
{
private Dictionary<int, int> integerDictionary;
public TimeSpan InstantiationTime()
{
TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_));
return iStopwatchType.TimeElapsed;
}
private void InstantiationTime_()
{
integerDictionary = new Dictionary<int, int>();
}
public TimeSpan WriteTime()
{
TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_));
return iStopwatchType.TimeElapsed;
}
private void WriteTime_()
{
number = 0;
for (int i = 0; i < numberOfElements; i++)
{
integerDictionary.Add(number, number);
number++;
}
}
public TimeSpan ReadTime(LoopType dataStructureLoopType)
{
switch (dataStructureLoopType)
{
case LoopType.For:
ReadTimeFor();
break;
case LoopType.Foreach:
ReadTimeForEach();
break;
}
return iStopwatchType.TimeElapsed;
}
private void ReadTimeFor()
{
TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_));
}
private void ReadTimeFor_()
{
for (int i = 0; i < numberOfElements; i++)
{
number = integerDictionary[i];
}
}
private void ReadTimeForEach()
{
TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_));
}
private void ReadTimeForEach_()
{
foreach (KeyValuePair<int, int> i in integerDictionary)
{
number = i.Key;
number = i.Value;
}
}
}
public class ListTimeTest : DataStructureTimeTest, IDataStructureTimeTest
{
private List<int[]> integerList;
public TimeSpan InstantiationTime()
{
TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_));
return iStopwatchType.TimeElapsed;
}
private void InstantiationTime_()
{
integerList = new List<int[]>();
}
public TimeSpan WriteTime()
{
TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_));
return iStopwatchType.TimeElapsed;
}
private void WriteTime_()
{
number = 0;
for (int i = 0; i < numberOfElements; i++)
{
integerList.Add(new int[2] { number, number });
number++;
}
}
public TimeSpan ReadTime(LoopType dataStructureLoopType)
{
switch (dataStructureLoopType)
{
case LoopType.For:
ReadTimeFor();
break;
case LoopType.Foreach:
ReadTimeForEach();
break;
}
return iStopwatchType.TimeElapsed;
}
private void ReadTimeFor()
{
TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_));
}
private void ReadTimeFor_()
{
for (int i = 0; i < numberOfElements; i++)
{
number = integerList[i].ElementAt(1);
}
}
private void ReadTimeForEach()
{
TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_));
}
private void ReadTimeForEach_()
{
foreach (int[] i in integerList)
{
number = i.ElementAt(1);
}
}
}
Solution 5
An array access in C# is a simple index operation, whereas a dictionary is a hash table lookup. Arrays are comparable to C++ arrays except for some small overhead of bounds-checking performed by the language.
If you're not going to be changing the contents, I'd use an array for data size, if nothing else.
Valentin
Updated on July 09, 2022Comments
-
Valentin almost 2 years
I wanted to know is C# array has a constant access speed?
I need to store 1000 items in static array, that will be initialized during server startup. This array will be used readonly, so there will be no changes to array.
Should I use a simple C# array (new MyClass[]) or Dictionary instead.I am really new to C# and trying to understand how C# arrays access works.
Can they be compared to c++ arrays by speed?