# Performance Optimization of n:1-mapping

I am filtering a List (childList) based on the contents of another List (parentList).

The parentList can contain 0-n entities where items of the childList are referenced by an ID (btw. ID is in this case a string, you could also call it "Name" or whatever you like). I want to filter the childList in a way that the result is all elements that have at least one entry in the parentList.

The obvious solution is:

List<childItem> resultList = new List<childItem>();

foreach(var childItem in childList){
foreach(var parentItem in parentList){
if(childItem.ID.Equals(parentItem.ChildID,StringComparison.InvariantCultureIgnoreCase){
break; // search for next childItem
}
}


What I have done by now is:

// Group by childID and create List with all relevant IDs
var groupedParentList = parentList.AsParallel().GroupBy(p => p.ChildID).Select(group => group.First()).ToList();

// Filter childList on groupedParentList
var result = childList.AsParallel().Where(child => groupedParentList.AsParallel().Count(parent => parent.childID.Equals(child.ID, StringComparison.InvariantCultureIgnoreCase)) > 0).ToList();


But it's lasting rather long. The parentList contains about 75k entries and the childList about 4.5k entries. I just can't believe it actually takes time - imo this should be done in almost no time?

Maybe I am on the wrong track or am I missing some obvious performance-stopper?

Btw.: I have chosen the names parent- and childList just as an example. It's actaully no parent-child-relation.

Additional Question: Could it be faster to direcly check if the parentList contains the childList-Item? Something a lá:

var test = childList.RemoveWhere(child => !parentList.Contains(item => item.childID.Equals(child.ID));


So I would just skip the grouping? Any suggestions/ideas?

• Can't you change the entities so that they don't use IDs, but direct references? Jul 16, 2012 at 13:50
• Unluckily - no. Let's say I have no access to the structure itself. Jul 16, 2012 at 14:02

First red flag; you're using Count(predicate) > 0. The Count() overload that takes a predicate must iterate over all elements of the parent enumerable to determine the correct count, and you're telling it to do so for each element of the child list. You simply want to know if at least one of those elements matches; for that, the Any() overload which accepts the same parameter will be faster, because it will quit as soon as it finds the first element that matches (unfortunately the worst-case of a match not existing will still require a full scan of the enumerable).

First step to improving this: Instead of grouping, select a list of distinct child IDs from the parent list. This process will produce strings instead of groups of larger ParentItems, which should hopefully reduce the amount of "heap-thrashing" required to generate the groups only to reduce it down to a much smaller collection. You only ever need the child IDs from the parent list anyway.

// Group by childID and create List with all relevant IDs
var childrenOfParents = parentList.AsParallel()
.Select(p => p.childId)
.Distinct()
.OrderBy(x=>x)
.ToList();


Then, filter the child list based on the ID being in the derived list of child IDs:

// Filter childList on groupedParentList
var result = childList.AsParallel()
.Where(child => childrenOfParents
.Any(cid=>cid.Equals(child.ID, StringComparison.InvariantCultureIgnoreCase)))
.ToList();


I do not know about the culture-specific comparison behavior, but if it's at all possible to compare the strings verbatim (even ToLower()ed), it would likely be preferable performance-wise.

Other things that may help include building custom extension methods that make certain assumptions:

• Naive grouping or deduping (Distinct()) of an enumerable is an N2-complexity operation (compare each element to a list of already-processed elements and remove if it exists). This is the least efficient part of the first query. Deduping of a list sorted by the same projection that must be de-duped is linear (compare each element to the previous one and remove if equal). You will be able to dedupe the list of child IDs more efficiently than PLinq's default implementation if you know the list is sorted by the same projection (in this case the identity projection) that you must dedupe.

public IEnumerable<TObj> SortAndDedupe<TObj, TProj>(this IEnumerable<TObj> input, Func<TObj, TProj> projection)
{
sortedInput = input.OrderBy(projection);

TProj last;
var init = false; //default(T) might be valid
foreach(var element in sortedInput)
{
if(!init || !projection(element).Equals(last))
{
init = true;
last = projection(element);
yield return element;
}
}
}

...

// Your first query is now an NlogN operation
var childrenOfParents = parentList.AsParallel()
.Select(p => p.childId)
.SortAndDedupe(s=>s)
.ToList();

• Naive searching for elements that match a predicate is linear, which makes the second query N2-complexity. In your case, with a sorted list of childID strings being searched for a value that is equal to a passed projection, you can use a logarithmic binary search:

public bool IsInSortedList(this T toFind, List<T> collection)
where T: IComparable<T>
{
var max = collection.Count - 1;
var min = 0;
var idx = (max-min)/2;

while(max >= min)
{
if(collection[idx].CompareTo(toFind) == 0) return true;
else if(collection[idx].CompareTo(toFind) < 0) //search right
min = idx+1;
else if(collection[idx].CompareTo(toFind) > 0) //search left
max = idx-1;

idx = (max-min)/2 + min;
}

return false;
}

...

//This query is now an NlogN as well
var result = childList.AsParallel()
.Where(child => child.IsInSortedList(childrenOfParents)
.ToList();

• Thanks for this awesome answer, it really taught me, to read and learn more about datastructures and algorithms. A few Questions: In SortAndDedupe(..), I needed to initialize the TProj last with default(T) and I had to reverse your if() in the while(). By doing this I removed the init-bool. (Otherwise I always got only one result back). Did I implement it wrong, or was it just a typo? (I just want to make sure, I did it right! :) ) Btw. your solution is great (I will use it), but it also takes 3 sec. - the same as my initial try :D Jul 17, 2012 at 7:49
• The condition that the current element must equal the last should actually be that the current element does not equal the last one. Use of default(TProj) to initialize last, thus doing away with init, is OK as long as you don't use this in a situation where the default value of a value type (e.g. zero for numeric types) is valid. In your specific case, you're using string IDs, but if they were numbers, you could see a problem. Another way to solve it is to yield return the first element (setting it to last) before entering the loop. Jul 17, 2012 at 14:32