2
\$\begingroup\$

I'm using VS 2008. I pass a List<T> a using ref, along with another List<T> b.

I need to cycle thru List<T> b, which contains around 200,000 items, and for each item in b, it it matches criteria in a, which contains 100,000 or more items, and update it.

public static void UpdateList(ref List<ExampleT> a, List<ExampleT> b)
{

    var count = 0;
    for (int i = 0; i < b.Count; i++)
    {

        foreach (var z in a.FindAll(x => x.MatchA == b[i].MatchA && x.MatchB == b[i].MatchB))
        {
            z.ToUpdate = b[i].ToUpdate;
            count++;
        }
        if(count >= 10000)
            break;
    }
}

Now, the only reason I added count was so that once 10000 items in a have been updated, the loop will stop, otherwise it will take a very long time to go thru all of the items. Even by limiting it like this, it still takes around 3 min.

For the sake of the example, T in this case is an object similar to the following:

public class ExampleT
{
public string MatchA {get;set;}
public string MatchB {get;set;}
public double? ToUpdate {get;set;} //in List a this will ALWAYS be null until it gets updated in the foreach
}

Is there a way I can make this more efficient?

\$\endgroup\$
4
  • 2
    \$\begingroup\$ You are essentially doing a join and then an update. I suspect that this can be written shorter using LINQ over objects syntax. Let me try to look it up. It should not be hard to analyze the complexity of this. Ok, this should hopefully be of some help: stackoverflow.com/questions/709560/… LINQ can be slower than bare loops, but it often does a pretty good job. \$\endgroup\$ – Leonid Apr 19 '12 at 16:01
  • 3
    \$\begingroup\$ I would also look into PLINQ as you have a lot of data to plow through. \$\endgroup\$ – Leonid Apr 19 '12 at 16:07
  • 1
    \$\begingroup\$ Hm, using your example and stuffing various random data into the objects into the two lists of the sizes you specify, it executes in less than 1/100 second on my machine. I have my doubts that my box is 18,000 times faster than yours, so something else must be at work here. \$\endgroup\$ – Jesse C. Slicer Apr 19 '12 at 17:10
  • 4
    \$\begingroup\$ There doesn't seem to any reason to pass a by reference in your code. \$\endgroup\$ – svick Apr 19 '12 at 19:20
3
\$\begingroup\$

Your code is O(n m), where n is the length of a and m is the length of b.

You could make it O(n + m) (assuming only a small number of items from a match each item in b) by using a hash table. One possible way to do this is to use ToLookup():

var aLookup = a.ToLookup(x => new { x.MatchA, x.MatchB });

foreach (var bItem in b)
{
    foreach (var aItem in aLookup[new { bItem.MatchA, bItem.MatchB }])
        aItem.ToUpdate = bItem.ToUpdate;
}

Another way to do basically the same thing would be using join:

var pairs = from bItem in b
            join aItem in a
              on new { bItem.MatchA, bItem.MatchB } equals new { aItem.MatchA, aItem.MatchB }
            select new { bItem, aItem };

foreach (var pair in pairs)
    pair.aItem.ToUpdate = pair.bItem.ToUpdate;

Also, you should really use better variable names.

\$\endgroup\$
1
  • \$\begingroup\$ variable names where obviously renamed for the purposes of this post... \$\endgroup\$ – RJP Apr 19 '12 at 20:47
2
\$\begingroup\$

Not knowing the full extent of the data types behind the MatchA, MatchB and ToUpdate properties, it'll be difficult to give an answer which completely solves your performance issues. However, one potential optimization could be realized in your foreach line as such:

foreach (var z in a.FindAll(x => x.MatchA == b[i].MatchA && x.MatchB == b[i].MatchB && x.ToUpdate != b[i].ToUpdate))

This would limit the set brought back to only those members that actually need their ToUpdate set rather than just setting them whether they need to or not.

\$\endgroup\$
2
  • \$\begingroup\$ I don't think this would help. You're trading one assignment for one condition, that shouldn't change much. \$\endgroup\$ – svick Apr 19 '12 at 19:53
  • \$\begingroup\$ The OP since updated the question and having it makes no more sense at all since it's true 100% of the time. \$\endgroup\$ – Jesse C. Slicer Apr 19 '12 at 20:07

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.