for in for优化

Question

我正在尝试优化这段代码：

   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
       }
     }
   }

如果ids.count是1600，Maps.Count是300000，处理大约需要10分钟。

我尝试过LINQ，但效果也好不到哪里去：

   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.

有没有人能给我一个更好的解决方案，如果可能的话，解释一下为什么linq在这种情况下不是更快？

谢谢

Answer 1

你有O(countIds * countMaps)的复杂度，如果你把所有的地图放在2个字典中，按源和目的地索引，你会得到O(countIds + countMaps)。