tags:

views:

163

answers:

7

I have List of (PatchFacilityManager) and a List of (Int) facilityManagerId. I want to make the below code efficient. Is there any way to remove these two foreach loop.

 foreach (PatchFacilityManager PM in patchFacilityManager)
 {
     foreach (int FM in facilityManagerId)
     {
         if (PM.FacilityManagerId == FM)
         {
             PM.IsSelected = true;
         }
     }
 }
+1  A: 
patchFacilityManager
.Where(c => facilityManagerId.Contains(c.FacilityManagerId))
.ForEach(c => c.IsSelected = true);
Matteo Mosca
Won't that just do something like the code in the question behind the scenes?
Bart van Heukelom
Well, it's sort of a many-to-many compare. Compare every item of A with every item of B and for each match, set a property of A. That's how you say it in "pseudo-code". Anyway I think the Contains method is more efficient than the nested loops.
Matteo Mosca
@Matteo: There's no built-in `ForEach` method applicable to `IEnumerable<T>` and that's what your `Where` call returns. `ForEach` is an instance method on `List<T>` so you'd need to call `ToList` first, and that's not going to make things more efficient!
LukeH
You're right, I forgot about that just because I use some custom extension methods, and one of those is ForEach for IEnumerable<T>. My bad not to mention that.
Matteo Mosca
+7  A: 

Here's one way,

    foreach (PatchFacilityManager PM in patchFacilityManager)
    {
        PM.IsSelected = facilityManagerId.Contains(PM.FacilityManagerId);
    }

EDIT

This solution is efficient in two three ways IMHO as compared to the code given in the question.

First, it does not test for the condition and the result of the expression is straight away assigned into PM.IsSelected. As per LukeH's comment, it is mandatory to not set the PM.IsSelected to false, so the condition is unavoidable. However this improvement is applicable if the asked needs to set it to false. . From question asker's comment, his case seem to go right with this optimization. So no need for conditional assignment.

Second, it does not iterate through whole list, since List.Contains(int), returns true and come out of loop on the first occurrence of the int passed in argument.

Third, when framework gives you the functionality List.Contains(int), then why re-invent the wheel. So from maintenance perspective this is also more efficient.

this. __curious_geek
+1 this is the way I'd do it. Depending on how big the IDs list is, you could also remove ones that have already been matched to make the list smaller - though you'd be hard pressed to prove that it actually makes a difference.
Adam
I think you should use a `new HashSet<int>(facilityManagerId)` for the `.Contains` calls. Am I wrong here?
Jens
It is more efficient since it gets rid of the condition. and secondly, .Cotains() will return true, the moment it finds the first match where in case of the code in question, it will iterate through all elements which is completely unnecessary.
this. __curious_geek
Yes, this won't be any more efficient. List<T>.Contains is an O(n) operation. You'd need to do some other form of data structure to reduce the time cost of the search.
Mel Harbour
@LukeH: surely it will be more efficient... The inner foreach is guaranteed to test every element in facilitymanagerID whereas the contains method would, I assume, stop looking after it has found a value. which would on average half the time. And that is assuming that contains has no other optimisations (not got time to go rummaging around its implementation right now).
Chris
@Chris, that what I'm saying. That is why I used List<T>.Contains() edited my answer.
this. __curious_geek
@this.__curious_geek: Removing the conditional means that your code has different logic to the code given in the question. The original will *never* set `IsSelected` to false, yours could.
LukeH
@Mel Harbour: Its the same Order of efficiency but that doesn't mean one way won't be quicker...
Chris
The only optimisation is the fact that it stops when it finds the element. The lack of a termination condition in the loop is a bug in the above code. The internal implementation of List<T>.Contains is fundamentally no faster than the method above. If you genuinely want it to run faster, you need to use HashTables, for instance. HashTable.Contains, for instance, runs in O(1) time. Yes, you have the overhead of creating the HashTable, but that's likely to be significantly lower than the overall cost of the algorithm above.
Mel Harbour
@LukeH: Thanks for spotting the bug. Now it will.
this. __curious_geek
@this.__curious_geek In answer to your justifications:1 - Your algorithm does something fundamentally different (see LukeH's comment).2 - Yep. A good efficiency upgrade.3 - Good idea to use Framework methods, but use the right one for the job.
Mel Harbour
@Mel: Yes, I agree with you. I have edited my answer.
this. __curious_geek
@Mel Harbour: I see your point. Thanks for taking the time to explain. :)
Chris
@Luke, @Mel: Updated the answer based Question asker's comment. Thanks for outlining the fact.
this. __curious_geek
I wish people would stop voting this answer up. It runs in about the same time as the original solution, and there is a solution from LukeH that runs HUGELY faster.
Mel Harbour
A: 

You could store the facility manager id's in an array in sorted order, and then look them up using BinarySearch instead of a foreach.

Stephen Cleary
A better solution. BinarySearch is O(log n), but the HashSet version still wins as it's O(1).
Mel Harbour
Technically, BinarySearch is (log n) worst time; HashSet is only *amortized* O(1) with (n) worst time. That said, I agree that HashSet is a better solution.
Stephen Cleary
+1  A: 
var ids = new HashSet<int>(facilityManagerId);
foreach (PatchFacilityManager pfm in patchFacilityManager)
{
    if (ids.Contains(pfm.FacilityManagerId))
        pfm.IsSelected = true;
}
LukeH
Yep, much neater than my version below. Definitely +1!
Mel Harbour
This is the solution that should have been marked as the answer. Profiling it versus the accepted answer shows that it's ridiculously faster for a reasonable number of items in the collections. VOTE THIS ONE UP!!!
Mel Harbour
A: 
patchFacilityManager
   .Where(m => facilityManagerId.Contains(m.FacilityManagerId))
   .ToList()
   .ForEach(m => m.IsSelected = true);

or

patchFacilityManager
   .Join(facilityManagerId, m => m.FacilityManagerId, f => f, (m,f) => m)
   .ToList()
   .ForEach(m => m.IsSelected = true);
goofballLogic
A: 

Another variant using LINQ syntax:

var match = for PM in patchFacilityManager
            join FM in facilityManager on PM.FacilityManagerId equals FM
            select PM;
foreach(var PM in match)
{
   PM.IsSelected = true;
}
AZ
A: 

Just for fun and outside the box - an approach when the lists are sorted:

static void Main(string[] args)
        {
            List<int> nums = new List<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
            List<int> ids = new List<int>(new int[] { 2, 4, 5 });

            for (int i = 0, j = 0; i < nums.Count && j < ids.Count; i++)
            {
                int num = nums[i];
                int id = ids[j];

                if (num == id)
                {
                    Console.WriteLine("Match = " + id);
                    j++;
                }
            }

            Console.ReadLine();
        }

I presume no knowledge of the performance benefit or detrement of this idea. Of course you can modify this to use a main foreach for the numbers and you manually use the Enumerator of the IDs inside the main foreach if you have allergies to fors.

Adam