5

I would like to ask whether there's an elegant and efficient way to merge two lists of MyClass into one?

MyClass looks like this:

  • ID: int
  • Name: string
  • ExtID: int?

and the lists are populated from different sources and objects in lists do share ID, so it looks like that:

MyClass instance from List1
ID = someInt
Name = someString
ExtID = null

And MyClass instance from List2

ID = someInt (same as List1)
Name = someString (same as List1)
ExtID = someInt

What I basically need is to combine these two lists, so the outcome is a list containing:

ID = someInt (from List1)
Name = someString (from List1)
ExtID = someInt (null if no corresponding item - based on ID - on List2)

I know I can do this simply using foreach loop, but I'd love to know if there's more elegant and maybe preferred (due to performance, readability) method?

1
  • write a Merge function that combines two instances with the same ID into one - then you can concat the lists, group by id and finally fold/reduce over the groups using your merge function - that's how I would do it for readability - for performance you are probably fine with sorting and a loop
    – Random Dev
    Nov 4, 2015 at 10:36

3 Answers 3

3

There are many approaches depending on what is the priority, ex. Union + Lookup:

//this will create a key value pairs: id -> matching instances
var idMap = list1.Union(list2).ToLookup(myClass => myClass.ID);
//now just select for each ID the instance you want, ex. with some value
var mergedInstances = idMap.Select(row => 
      row.FirstOrDefault(myClass => myClass.ExtId.HasValue) ?? row.First());

The benefit of above is that it will work with whatever amount of whatever lists even if they contain many duplicated isntances and then you can easily modify the conditions of merging

A small improvement would be to extract a method to merge instances:

MyClass MergeInstances(IEnumerable<MyClass> instances){
     return instances.FirstOrDefault(myClass => myClass.ExtId.HasValue) 
          ?? instances.First(); //or whatever else you imagine
}

and now just use it in the code above

 var mergedInstances = idMap.Select(MergeInstances);

Clean, flexible, simple, no additional conditions. Performance wise not perfect, but who cares.

Edit: since performance is the priority, some more options

  1. Do a lookup like above but only for the smaller list. Then iterate through the bigger and do the needed changes O(m log m) + O(n). m - smaller list size, n- bigger list size - should be fastest.

  2. Order both lists by elements ids. Create a for loop, that iterates through both of them keeping current index to the element with same id for both lists. Move index to the next smallest id found in both list, if one has it only, move only this on. O(n log n) + O(m log m) + O(n);

7
  • Will it work faster than foreach loop on List2 to corresponding items in List1 and set the value? ;> If not, then since it's hidden inside a private method of library, I wouldn't mind using foreach loop instead to gain more performance since I don't know how big the lists can grow and how often this will used. I may have stated it wrong way, but the priority is performance.
    – pzaj
    Nov 4, 2015 at 10:48
  • 1
    If for each element you need to search through the elements of the other lists, then you get O(n^2) complexity, the above one will be faster since the lookup is O(log n) * O(n) of Select which is a foreach loop in fact O(n log n) vs O(n^). My wins ;). Using Lookup table (dictionary/map) is a way to go anyway. And you get flexibility as well. If you can improve existing solution you could think about providing a dictionary from the beginning instead of the list even.
    – mikus
    Nov 4, 2015 at 10:55
  • 1
    you can create a lookup (or dictionary) on one of the list and then just foreach the second one using the lookup to find the values quickly. Also you can think about ordering both lists and do a smart loop that will only go once trough both lists O(n log n) + O(n).
    – mikus
    Nov 4, 2015 at 10:58
  • 1
    If name is unique you can base on name instead of ID from the beginning. :) If it is not, then it doesnt help and also doesnt matter for the merging algorithm too. So either you do as above, or you make lookup out of smaller list and foreach the other (I'd say its the fastest way). Or you sort both by id (or name), and do a one for loop that iterates through both of the list at the same time incrementing indexes in a way that they always point to same element id. I'll include it in the answer
    – mikus
    Nov 4, 2015 at 11:13
  • 1
    hard to say if it will be faster, it won't pack elements in the lists (or any other enumerable) so it should be faster, for sure, if you expect one element only, then it's suitable one to use :)
    – mikus
    Nov 4, 2015 at 11:41
2

Is this what you want

var joined = from Item1 in list1
         join Item2 in list2
         on Item1.Id equals Item2.Id // join on some property
         select new MyClass(Item1.Id, Item1.Name, Item1.ExtID??Item2.ExtID);

Edit: If you're looking for an outer join,

var query = from Item1 in list1
            join Item2 in list2 on Item1.Id equals Item2.Id into gj
            from sublist2 in gj.DefaultIfEmpty()
            select new MyClass(Item1.Id, Item1.Name, sublist2??string.empty);

Readability wise, using foreach loop is not a too bad idea..

2
  • since it's an inner join looks like it won't work if some id's are missing in one of the lists
    – mikus
    Nov 4, 2015 at 10:46
  • yeah..true..added outer join case
    – Godsent
    Nov 4, 2015 at 11:00
-2

I'd sugest creating the foreach loop in a method of that class, so everytime you needed to do such thing you'd use something like

instanceList1.MergeLists(instanceList2)

and with this method, you could control everything you wanted withing the merge operation.

2
  • @mikus LINQ does use iteration and iterators, so the comment about foreach doesn't apply. On the other hand, write your own function isn't a good answer when the OP asks how to write that function. Perhaps this should be deleted and re-posted as a comment ? Nov 4, 2015 at 10:39
  • Well, I just assumed he knew how to do the function and I though this would be the better aproach. (He said he didnt want the foreach yes, but I though he meant like, he doesn't want to do it everytime he needs to do the merge)
    – Paulo Lima
    Nov 4, 2015 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.