1
\$\begingroup\$

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){
            resultList.Add(childItem); //found entity
            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?

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

1 Answer 1

3
\$\begingroup\$

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).

You're also parallelizing parallelization. While parallel is good, threads waiting on threads waiting on threads can easily result in an algorithm that is bound by the ThreadPool's ability to spin up new threads (the default is a 250ms wait for each new thread after a predetermined number of "readily-available" threads have been scheduled). So, after creating, let's say 10 threads for this algorithm, most of which will be waiting on sub-threads, the ThreadPool will only create four new threads per second. Let's say the TPL begind the PLinq library thinks that one thread per 100 elements of both collections is necessary. On a collection of 4500 elements, for each of which a comparison of 4500 more elements is necessary, the ThreadPool could schedule two thousand worker threads to execute. After 10 of them are created near-instantaneously, only four more per second will be created as long as at least 10 are running, meaning this algorithm will take up to 500 seconds just to schedule all the necessary threads. The more "instantaneous" threads you tell the ThreadPool to spin up before queueing them, the more cache-thrashing you'll do forcing the CPU to juggle all these threads.

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();
    
\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$
    – basti
    Jul 17, 2012 at 7:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – KeithS
    Jul 17, 2012 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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