Multiply Indexed Keyed Collection for .NET

Aug 04, 2014

** UPDATE 2014-08-17: According to our benchmark results, MultiplyIndexedKeyedCollection is in some scenarios thousands of times faster than the standard .NET-collection!

MultiplyIndexedKeyedCollection is a lightweight collection with high read-performance released to the public domain. The key advantages compared to the standard KeyedCollection are:
  • Support for multiple indexes, which means high read performance
  • Support for one-to-many mapping (as well as one-to-one mapping)
  • Released to the public domain, so you can do what you want with the source code
There is a NuGet package, a sample NuGet package and the source code is available at GitHub. The disadvantage with MultiplyIndexedKeyedCollection is that when you have more indexes, write performance will decrease. The reason is that when you add items, these items are indexed (just like with indexes in a database table). Hence, if you have collections that you add a lot of items to that you don’t want to read, perhaps you should not use MultiplyIndexedKeyedCollection.

Background

So, what is a keyed collection and how does it compare to a dictionary? Msdn explains this clearly:
… a collection whose keys are embedded in the values.
However, a dictionary allows you to use keys that are not embedded in the values. (A mulptiply indexed dictionary would be cumbersome to work with, because then you would have to add a lot of keys each time you add an item to the dictionary.) Since the standard KeyedCollection only supports one key, read performance is only high when you get items based on that single key. Also, it doesn’t support keys that map to multiple values. But you can use MultiplyIndexedKeyedCollection instead.

Comparing KeyedCollection to MultiplyIndexedKeyedCollection

Assume you need a collection of objects of type CountryOrRegionGdpData:
public class CountryOrRegionGdpData
{
    public string CountryCode { get; set; }
    public string CountryName { get; set; }
    public decimal GdpYear1960 { get; set; }
    public decimal GdpYear2010 { get; set; }
}
And assume that you want to get items based on these keys/rules:
  • Get single item by country code
  • Get single item by country name
  • Get all items that increased the GDP by at least 5x
  • Get all items that increased the GDP by at least 10x
  • Get all items that increased the GDP by at least 20x

KeyedCollection sample code

Since KeyedCollection only supports one key, we use the country code as the key. The collection type definition:
public class StandardKeyedCollectionOfCountryOrRegionGdpData : KeyedCollection<string, CountryOrRegionGdpData>
{
    protected override string GetKeyForItem(CountryOrRegionGdpData item)
    {
        return item.CountryCode;
    }
}
Assuming we have a variable called standardKeyedCollectionOfCountryOrRegionGdpData that is of type StandardKeyedCollectionOfCountryOrRegionGdpData, we add items like this:
standardKeyedCollectionOfCountryOrRegionGdpData.Add(item);
And we get the items we want like this:
CountryOrRegionGdpData itemByCode = standardKeyedCollectionOfCountryOrRegionGdpData["SWE"];
CountryOrRegionGdpData itemByName = standardKeyedCollectionOfCountryOrRegionGdpData.Single(q => q.CountryName == "Sweden");
IEnumerable<CountryOrRegionGdpData> itemsByHasFiveDoubled = standardKeyedCollectionOfCountryOrRegionGdpData.Where(countryOrRegionGdpData => countryOrRegionGdpData.GdpYear2010 >= countryOrRegionGdpData.GdpYear1960 * 5);
IEnumerable<CountryOrRegionGdpData> itemsByHasTenDoubled = standardKeyedCollectionOfCountryOrRegionGdpData.Where(countryOrRegionGdpData => countryOrRegionGdpData.GdpYear2010 >= countryOrRegionGdpData.GdpYear1960 * 10);
IEnumerable<CountryOrRegionGdpData> itemsByHasTwentyDoubled = standardKeyedCollectionOfCountryOrRegionGdpData.Where(countryOrRegionGdpData => countryOrRegionGdpData.GdpYear2010 >= countryOrRegionGdpData.GdpYear1960 * 20);

MultiplyIndexedKeyedCollection sample code

MultiplyIndexedKeyedCollection supports multiple keys:
public class MultiplyIndexedKeyedCollectionOfCountryOrRegionGdpData : MultiplyIndexedKeyedCollectionBase
{
    public readonly IndexedMapping<string, CountryOrRegionGdpData, CountryOrRegionGdpData> ByCountryCode;
    public readonly IndexedMapping<string, CountryOrRegionGdpData, CountryOrRegionGdpData> ByCountryName;
    public readonly IndexedMapping<bool, CountryOrRegionGdpData, IEnumerable<CountryOrRegionGdpData>> ByHasFiveDoubled;
    public readonly IndexedMapping<bool, CountryOrRegionGdpData, IEnumerable<CountryOrRegionGdpData>> ByHasTenDoubled;
    public readonly IndexedMapping<bool, CountryOrRegionGdpData, IEnumerable<CountryOrRegionGdpData>> ByHasTwentyDoubled;

    public MultiplyIndexedKeyedCollectionOfCountryOrRegionGdpData()
    {
        // Here we do not explicitly specify any equality comparer, so a default equality comparer will be used
        this.ByCountryCode = CreateAndRegisterIndexedOneToOneMapping(countryOrRegionGdpData => countryOrRegionGdpData.CountryCode);

        // When specifying null as equality comparer, a default equality comparer will be used (just like the previous case)
        this.ByCountryName = CreateAndRegisterIndexedOneToOneMapping(countryOrRegionGdpData => countryOrRegionGdpData.CountryName, null);

        // It is also possible to explicitly specify an equality comparer
        this.ByHasFiveDoubled = CreateAndRegisterIndexedOneToManyMapping(countryOrRegionGdpData => countryOrRegionGdpData.GdpYear2010 >= countryOrRegionGdpData.GdpYear1960 * 5, EqualityComparer.Default);
        this.ByHasTenDoubled = CreateAndRegisterIndexedOneToManyMapping(countryOrRegionGdpData => countryOrRegionGdpData.GdpYear2010 >= countryOrRegionGdpData.GdpYear1960 * 10, EqualityComparer.Default);
        this.ByHasTwentyDoubled = CreateAndRegisterIndexedOneToManyMapping(countryOrRegionGdpData => countryOrRegionGdpData.GdpYear2010 >= countryOrRegionGdpData.GdpYear1960 * 20, EqualityComparer.Default);
    }
}
Assuming we have a variable called multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData that is of type MultiplyIndexedKeyedCollectionOfCountryOrRegionGdpData, we add items like this:
multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData.Add(item);
And we get the items we want like this:
CountryOrRegionGdpData itemByCode = multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData.ByCountryCode["SWE"];
CountryOrRegionGdpData itemByName = multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData.ByCountryName["Sweden"];
IEnumerable<CountryOrRegionGdpData> itemsByHasFiveDoubled = multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData.ByHasFiveDoubled[true];
IEnumerable<CountryOrRegionGdpData> itemsByHasTenDoubled = multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData.ByHasTenDoubled[true];
IEnumerable<CountryOrRegionGdpData> itemsByHasTwentyDoubled = multiplyIndexedKeyedCollectionOfCountryOrRegionGdpData.ByHasTwentyDoubled[true];

Tags:

No comments

Leave a Reply

Your email address will not be published. Required fields are marked *