Quick list search <T>

Question

I have two general lists. Let them say that they are List< A > and List< B > .

Class A has a property whose type is List< B > . This property contains objects of type B that are filtered by some other objects 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 would like to add the entire object B to the list to object A (to the Something3 property), where you can say object A.Something1 == B.Anything1 .

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

(VS2010; C # ;. Net4)

Answer 1

B in the Anything1 property and put into the dictionary. Then you can execute cycle A and effectively select list B :

 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 is as much data as you mentioned, the performance of the select and insert operations is performed in the following order.

From Common Dictionaries in C # :

• Dictionary<int,A>

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

• SortedDictionary<int,A>

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

• SortedList<int,A>

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

Note that if the amount of data is relatively small, then List<int, A> will be good. (Depending on your data size, the order above will be rebuilt.)

Meanwhile, you need to consider Collection type capacity in C # . The Collection type resizes, so if there is no size, the collection is recreated as larger than before and the elements are reinserted. This moment tells you that if you already know the size of the collection, you should set the capacity in the Collection constructor.

Answer 3

I would use a map check, if it exists in list B, before adding to list A

Answer 4

Here is an alternative approach that uses LINQ more efficiently, rather than just replacing lists in each A Use a group join and add the elements in each group to the corresponding A

 List<A> myAs = ...; List<B> myBs = ...; var pairs = from a in myAs join b in myBs on a.Something1 equals b.Anything1 into TheseBs select new { A = a, TheseBs }; foreach (var pair in pairs) { pair.A.Something3.AddRange(pair.TheseBs); }