Josh's Submission To The Linq Challenge

Linq Challenge

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Class1
{
        // This first attempt is simply a straight port to linq.  I've kept the original optimization
        // that short circuited on the first matching id.
        static IList<ComponentInfo> ProcessWordComponentAndUploadInfos_ByJosh_Attempt1(
          DocumentCheckinJobInfo jobInfo,
          List<ComponentInfo> componentInfos)
        {
            if (!jobInfo.IsNewDocument)
            {
                var e = from dc_group in jobInfo.Document.DocumentComponentGroups
                        from dc in dc_group.DocumentComponents
                        // Any() will short circuit on the first match
                        where !componentInfos.Any(x => x.ComponentId == dc.Id)
                        select new ComponentInfo
                                   {
                                       ComponentTitle = dc.Title, 
                                       ComponentId = dc.Id, 
                                       RequestJobDocumentUploadItemStatusType = Business.RequestJobDocumentUploadItemStatusType.Deleted
                                   };
                return e.ToList();
            }
            return new List<ComponentInfo>();
        }

        // Swapped out the full scan of componentInfos for a binary search (which is log(n) iirc).
        // This will only help if we can expect componentInfos to have more than a handful of items.
        static IList<ComponentInfo> ProcessWordComponentAndUploadInfos_ByJosh_Attempt2(
      DocumentCheckinJobInfo jobInfo,
      List<ComponentInfo> componentInfos)
        {
            if (!jobInfo.IsNewDocument)
            {
                // Extract the ComponentIds into a sorted list.
                var id_list = (from ci in componentInfos
                              orderby ci.ComponentId
                              select ci.ComponentId).ToList();
                
                var e = from dc_group in jobInfo.Document.DocumentComponentGroups
                        from dc in dc_group.DocumentComponents
                        // because the list is sorted we can use a fast BinarySearch
                        where id_list.BinarySearch(dc.Id) < 0 // assuming default IComparer for Ids is satisfactory. 
                        select new ComponentInfo
                                   {
                                       ComponentTitle = dc.Title, 
                                       ComponentId = dc.Id, 
                                       RequestJobDocumentUploadItemStatusType = Business.RequestJobDocumentUploadItemStatusType.Deleted
                                   };
                return e.ToList();
            }
            return new List<ComponentInfo>();
        }

    // My next idea would be to explore parallelism.  But that's only going to help if we're talking about 
    // big sequences.  Like in the 1000s or 10,000s.  Anything shorter and we'd probably just waste the time task switching.

    // This violates the constraints of your problem (answer in linq), but if we're still not fast enough
    // then I'd say these ComponentInfos look like something stored in a table.  Make a single query against that
    // table to return all the missing ids in one fell swoop.
    //
    // select Id from ComponentInfo where Id not in (<list of ids from all ComponentInfos in jobInfo>)
}