Удаление итераций списка вложений для повышения производительности

Question

У меня есть несколько списков, которые мне нужно перебрать, чтобы выполнить вычисление. Таким образом, List1 - это список начальных и конечных точек дороги (идентификаторов), а List2 - это список отдельных выборок скорости для этих конечных точек (для каждого набора конечных точек имеется несколько выборок скорости). Список1 определяется следующим образом:

class RoadwaySegment
{ 
   public int StartId {get; set;} 
   public int EndId {get; set;}
}

Список 2 определяется следующим образом:

class IndividualSpeeds
{ 
   public int StartHour {get; set;} 
   public int StartMin {get; set;} //either 0,15,30,or 45
   public int Speed {get; set;} 
   public int StartId {get; set;} 
   public int EndId {get; set;}
}

List3 является результатом моих расчетов и будет содержать средние скорости для участков дороги в List1 для каждого 15-минутного периода дня. List3 выглядит так:

class SummaryData
{ 
  public string SummaryHour {get; set;} 
  public string SummaryMin {get; set;} 
  public int StartId {get; set;} 
  public int EndId {get; set;} 
  public int AvgSpeed {get; set;}
}

В настоящее время для создания List3 я выполняю итерации по List1, затем по каждому 24-часовому периоду дня, затем по каждому 15-минутному интервалу в час. Для каждой из этих итераций я проверяю, должна ли отдельная выборка скорости в List2 быть включена в расчет средней скорости для моего сегмента дороги. Итак, это выглядит примерно так:

var summaryList = new List<SummaryData>();
foreach (var segment in RoadwaySegments)
{
   for(int startHour = 0; startHour < 24; startHour++)
   {
      for(int startMin = 0; startMin < 60; startMin+= 15)
      {
         int totalSpeeds = 0;
         int numSamples = 0;
         int avgSpeed = 0;

         foreach(var speedSample in IndividualSpeeds)
         {
            if((segment.StartId == speedSample.StartId)&&(segment.EndId == speedSample.EndId)&&(speedSample.StartHour == startHour)&&(speedSample.StartMin == startMin))
            {
               if(speedSample.Speed > 0)
               {
                  totalSpeeds += speedSample.Speed;
                  numSamples += 1;
               }
            }
         }
         SummaryData summaryItem = new SummaryData {SummaryHour = startHour, SummaryMin = startMin, StartId = segment.StartId, EndId = segment.EndId, AvgSpeed = totalSpeeds/numSamples;
         summaryList.Add(summaryItem);
      }
   }
}

Проблема с этим кодом заключается в том, что List1 может иметь сотню сегментов проезжей части, но List2 может содержать миллион или более записей с образцами скорости, поэтому подтерации списка занимают очень много времени. Есть ли способ использовать GroupBy / LINQ для улучшения производительности и читабельности этого кода? Обратите внимание на условие включения скорости в среднее значение - она ​​должна быть больше 0.

Answer 1

Это не проверено, но я думаю, что это сработает:

from segment in RoadwaySegments
join sample in IndividualSpeeds on new { segment.StartId, segment.EndId } equals new { sample.StartId, sample.EndId } into segmentSamples
from startHour in Enumerable.Range(0, 24)
from startMin in new[] { 0, 15, 30, 45 }
let startMinSamples = segmentSamples
    .Where(sample => sample.Speed > 0)
    .Where(sample => sample.StartHour == startHour)
    .Where(sample => sample.StartMin == startMin)
    .Select(sample => sample.Speed)
    .ToList()
select new SummaryItem
{
    StartId = segment.StartId,
    EndId = segment.EndId,
    SummaryHour = startHour,
    SummaryMin = minute,
    AvgSpeed = startMinSamples.Count <= 2 ? 0 : startMinSamples.Average()
};

Основная идея состоит в том, чтобы выполнить итерацию списков сегментов и выборок один раз, создав группу выборок для каждого сегмента.Затем для каждой из этих групп вы генерируете часы и минуты и сводный элемент для каждой комбинации.Наконец, вы вычисляете среднюю скорость всех ненулевых выборок в комбинации час / минута.

Это не совсем идеально, потому что вы все еще повторяете выборки сегмента 24 * 4 раза, но это намного лучше, чемперебирать весь список образцов.Это должно привести вас на правильный путь, и, надеюсь, вы сможете оптимизировать этот последний шаг дальше.

Answer 2

Если вы используете .net 4, я бы предложил распараллелить это с Parallel Linq . Это смущающе параллельно параллельным сегментам Roadway.

Во-вторых, вместо вашей вложенной итерации по дочерним спискам я бы рекомендовал один раз повторить этот список и создать словарь List<IndividualSpeeds> с составным ключом StartId, EndId, StartHour и EndHour. Поиск в этом словаре будет намного быстрее по сравнению с повторением для каждого RoadwaySegment.

Answer 3

Ниже приведены ответы Криса и Брайана:
Поскольку вы говорите, что могут быть миллионы записей сэмплов скорости, вы просто не хотите повторять их больше, чем минимально возможный - то есть вы должны сгруппировать (используя GroupBy или Join операторы) их в соответствии с их началом час и минута Чем вы можете просто выполнить итерацию для каждой группы и добавить каждую примерную запись в некоторый словарь RoadwaySegments (что-то вроде Dictionary<RoadwaySegment, IEnumerable<IndividalSpeeds>>) и создать элементы Summary из этого словаря.