current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite
1

I'm trying to optimize this code:

 foreach (string id in ids)
 {
 MyClass x = myDictionary[id];
 foreach (var map in Maps)
 {
   if ( x.id == map.SourceId || x.id == map.DestionationId)
   {
       //add id to a hashset
   }
 }
}

If ids.count is 1600 and Maps.Count is 300 000 it takes around 10 minutes to process.

I've tried LINQ, but the results are not a lot better:

   var allIds = Maps.select(map => map.SourceId).Union(Maps.select(map => map.DestinationID)).Distinct();
   var toAdd = from id in Ids
           join mapId in AllIds on id equals mapid
           select id;
   //create hashset based on  toAdd collection.

Can anyone point me to a better solution and if possible explain why LINQ in this case isn't much more faster?

share|improve this question
1  
Why would you expect LINQ to be faster? And could you post all of the relevant code? It's hard to optimize code that you can't see. Also, could you explain what exactly do you want to achieve? –  svick Mar 18 '12 at 1:35
2  
LINQ is for increasing maintainability, not optimization. –  Jeff Mercado Mar 18 '12 at 1:36
    
Where did myDictionary come from and what does it do? What is the resulting HashSet for? What are you trying to do? –  Leonid Mar 18 '12 at 2:02

1 Answer 1

up vote 4 down vote

You are using an O(n*m) algorithm where an O(n+m) would do. Just create a dictionary: idToMap and then iterate over the ids. Then, if either dictionary ContainsKey(...) is true, then add to a 'HashSet`.

I do not know exactly what you are doing, but I do know that your complexity was off. Let's first get it to run fast wo LINQ ...

// O(m)
Dictionary<int,Map> idToMap = new Dictionary<int,Map>();
foreach(var map in maps)
{
    if (!idToMap.ContainsKey(map.SourceId))
    {
        idToMap[map.SourceId] = map;
        continue;
    }

    if (!idToMap.ContainsKey(map.DestionationId))
    {
        idToMap[map.DestionationId] = map;
    }
}

// O(n)
foreach (string id in ids)
{
    MyClass x = myDictionary[id];
    if (idToMap.ContainsKey(x.id))
    {
        // Add map or id to a hashset? But Why?
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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