Fast lookup of List<T>

Question

I have two generic lists. Let's say they are List< A > and List< B >.

ClassA has a property, which type is List< B >. This property contains B type objects, which are filtered by some other proerties of object A.

So:

class A{
  public int Something1;
  public int Something2;
  public List<B> Something3;
}

class B{
  public int Anything1;
  public int Anything2;
}

I'd like to add all object B as a list to object A (to Property called Something3), where let's say object A.Something1 == B.Anything1.

My question is: what is the most efficient way of adding List<B> items to List<A> items? Note, there can be hundreds of thousands of objects in both lists.

(VS2010; C#; .Net4)

Answer 1

Group the B's on the Anything1 property and put in a dictionary. Then you can loop through the A's and efficiently pick out the list of B's:

Dictionary<int, List<B>> beegroups = bees.GroupBy(b => b.Anything1).ToDictionary(g => g.Key, g => g.ToList());

foreach (A a in ayes) {
  List<B> group;
  if (beegroups.TryGetValue(a.Something1, out group)) {
    a.Something3 = group;
  }
}

Answer 2

If there are so many data as you mentioned, the the performance of selecting & inserting operations is the following order.

From the Generic Dictionaries in C#:

1. Dictionary<int,A>

   • Select: O(1) (meaning complexity)
   • Add: O(1) [or O(n)]
   • Based on a hash table

2. SortedDictionary<int,A>

   • Select: O(log n)
   • Add: O(log n)
   • Based on a binary search tree

3. SortedList<int,A>

   • Select: O(log n) [or O(n)]
   • Add: O(n)
   • Based on a sorted collection(sizable array)

Please note that if the number of data is relatively small, it List<int, A> would be good. (Depending on your data size, the order above would be rearranged.)

Meanwhile, you need to consider the capacity of the Collection type in C#. The Collection type is resizable, so if the size is lack, the Collection is recreated as bigger than before and the elements is inserted again. This point tells you that if you already know the size of the Collection, you should set the capacity at the Collection constructor.