What is the most effective collection for accessing an object based on two key options?

Question

I am trying to implement a large cache of objects (up to 500,000) and should have access to them in two different ways ...

The key for each item consists of three different lines; ItemNumber, PubCode and SizeCode. In some cases, I will cause a match on all three of these values ​​to return a single object. In other conditions, I will only match with ItemNumber and PubCode in order to return a collection of objects.

What is the best collection for this?

I only considered using a common list of objects (of which all three key values ​​are properties) and using LINQ to query it, however, I do not think that this will be the most efficient way of doing this especially when you are considering the size of the collection.

Any help would always be appreciated!

Answer 1

How many items are you likely to have for any combination of ItemNumber / PubCode? If the answer is "small enough," I will start with Lookup<ItemNumberPubCode, Value> (or Dictionary<ItemNumberPubCode, List<Value>> ), so if you are asked to find only two of them, you can get right in all matches. If you are asked to look at all three, you quickly get all matches of the first two, and then do an O (n) scan for any match using SizeCode.

(Here ItemNumberPubCode is a type that encapsulates ItemNumber and PubCode , it can be an anonymous type, Tuple<string, string> or a real type.)

If there can be many matches for a particular combination of ItemNumber / PubCode, then you may need Dictionary<ItemNumberPubCode, Dictionary<string, Value>> - this will allow you to efficiently search for all three, and from only two of them you can get dictionaries and use the Values property to find all matching values ​​for the pair.

Answer 2

Here is an easy way to do this using a dictionary of dictionaries. As John said, if this is necessary, it depends on the data.

 class TwoKeyDictionary<T> : Dictionary<string, Dictionary<string, T>> { public new IEnumerable<T> this[string key1] { get { return base[key1].Values; } } public T this[string key1, string key2] { get { return base[key1][key2]; } } public void Add(string key1, string key2, T item) { if (!base.ContainsKey(key1)) base[key1] = new Dictionary<string, T>(); base[key1].Add(key2, item); } } 

Answer 3

Basically, you can go and use the tree or hash structure for indexing (for example, a dictionary (Sorted)) - in your case you would use three of them. You just need to pinpoint what you need.

I don’t know your scenario, but I would suggest that it would be enough just to cache based on one property and just use regular database indexes (more or less the same as above) for other cases.

Answer 4

Since it is read-only, I would make a non-collection class that contains two collections.

 public class CacheOfManyObjects { private Dictionary<string, ObjectsToBeCached> ObjectsByItemPubSize{get;set;} //You might want to replace the IEnumerable<> with a List<> // but that depends on implementation private Dictionary<string, IEnumerable<ObjectsToBeCached>> ObjectsByItemPub{get;set;} public ObjectsToBeCached GetByItemPubSize(string tString); public IEnumerable<ObjectsToBeCached> GetByItemPub(string tString); } 

Objects will be added to each dictionary. You will need additional logic to create an object cache, but there is no real reason to have only 1 collection, since the collections themselves are small.