What is the optimal collection if the keys are sequential integers but not zero-based?
I am specifically referring to using years as keys, but the question is about any n-based sequential index.
Let's say I am looking at the apple harvest by year. I want to access my data in a year, for example:
var harvests = GetLast50YearsOfHarvestData();
//1991 was a great year for apples
harvests[1991].ApplesPicked ...
The obvious answer is to use a Dictionary.
var harvests = Dictionary<int, AppleHarvest>();
But I know that arrays are faster. Apple's harvesting software tends to be highly tunable for performance. I will not search, add or remove from my collection. I will only access keywords.
AppleHarvest[] harvests;
...
harvests[24] //1991 was a great year for apples
harvests[49] //wait what year is this? 2017?
I know my keys will always be sequential, no spaces, but working with an array requires additional logic to find out which year the zero index corresponds to. My performance could still be better, but I would rather not have to deal with this extra layer.
What are the options to achieve essentially an n-based array?
source to share
Create your own collection type:
public class SequentialKeyedCollection<T> : IEnumerable<T>
{
private T[] _innerArray;
private int _startIndex;
public SequentialKeyedCollection(int startIndex, int length)
{
_innerArray = new T[length];
_startIndex = startIndex;
}
public T this[int index]
{
get => _innerArray[index - _startIndex];
set => _innerArray[index - _startIndex] = value;
}
public int Length => _innerArray.Length;
public int IndexOf(T item)
{
int i = Array.IndexOf(_innerArray, item);
if (i < 0) return i; // Not found.
return i + _startIndex;
}
public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_innerArray).GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)_innerArray).GetEnumerator();
}
source to share
The option is to use the AppleHarves array, the element indices indicate the years:
AppleHarvest[] apples = new AppleHarvest[3000];
// 1991 was a great year for apples
apples[1991] = GetAppleHarvestForYear(1991);
Of course, there will be some kind of unused year at the beginning of the array, but this overhead is really low.
In terms of algorithmic complexity, reading from an array is an operation O(1)
. Reading from the dictionary is also done O(1)
, so the difference is only a constant factor, but arrays are faster.
source to share
To get a zero-based index, you can subtract the "base year" from any year:
harvest[year - START_YEAR]
This is easier to read than using the "magic number" and also more flexible as year
it is now a variable. You can even take this even further by encapsulating the array in a class and creating a getter method that takes a year as a parameter and internally subtracts and accesses the array.
source to share