Производительность итерации списка C #

Question

У меня есть цикл for, который выполняет 24 полных итерации, каждая из которых представляет один час дня, а затем проверяет каждый 15-минутный интервал в другом вложенном цикле for. Дополнительное гнездо проверяет список на значение часов и минут, а затем объединяет некоторые элементы в моем списке, если они соответствуют моим требованиям времени. Проблема в том, что мой список может содержать до 1 миллиона записей, что означает, что я пересекаю 1 миллион записей 24 * 4 раза.

Как я могу оптимизировать мой код для более быстрой работы в этом случае? Я знаю, что это, вероятно, можно упростить с помощью операторов LINQ, но я не уверен, что это сделает это быстрее. Вот пример того, что я делаю.

List<SummaryData> Aggregates = new List<SummaryData>();
for(int startHour = 0; startHour < 24; startHour++)
{
   for(int startMin = 0; startMin < 60; startMin+= 15)
   {
      int aggregateData = 0;
      //My ItemList can have up to 1 million records.
      foreach(ListItem item in ItemList)
      {
         if((item.time.Hour == startHour)&&(item.time.Minute == startMinute))
         {
            aggregateData += item.number;
         }
      }
         SummaryData aggregate = new SummaryData { SummaryId = item.id, TotalNumber = aggregateData
         Aggregates.Add(aggregate);

   }
}
class SummaryData
{
   public int SummaryId {get; set;}
   public int TotalNumber {get; set;}
}

Answer 1

Учитывая вашу логику, приведенную выше, вам нужно будет выполнить итерацию списка только один раз.Вы можете вкладывать свои циклы for в foreach и, вероятно, достигать лучшей производительности.Я бы также использовал Dictionary для хранения ваших агрегированных данных и основывал их ключ на общей минуте (то есть hour * 60 + minute).

Dictionary<int, AggregateDate> aggregate = new Dictionary<int, AggregateData>();

foreach(ListItem item in ItemList)
{
    int key = item.Hour * 60 + item.Minute;

    AggregateData data;

    if(!aggregate.TryGetValue(key, out data))
    {
        aggregate.Add(key, data = new AggregateData());
    }

    data.Number += item.Number;
}

Answer 2

Вместо того чтобы искать каждый Hour и Minute в каждом item, выполните итерации по ItemList всего один раз и действуйте на основе каждого item.time.Hour и item.time.Minute.

Answer 3

Я бы организовал данные примерно так:

(см. Также: http://ideone.com/dyfoD)

using System;
using System.Linq;
using System.Collections.Generic;

public class P
{
    struct DataItem
    {
        public System.DateTime time;
        public int number;
    }

    public static void Main(string[] args)
    {
        var ItemList = new DataItem[] {} ;
        var groups = ItemList
            .GroupBy(item => item.time.Hour * 60 + (item.time.Minute/15)*15 );
        var sums   = groups
            .ToDictionary(g => g.Key, g => g.Sum(item => item.number));


        // lookups now become trivially easy:

        int slot1900 = sums[1900];
        int slot1915 = sums[1915];
        int slot1930 = sums[1930];
    }
}

Answer 4

Ваше утверждение о проблеме немного нечетко.Похоже, что вам нужна сводка по идентификатору элемента, которая дает вам сумму всех номеров элементов, где временная метка попадает на целую четвертьчасовую границу.

Следующее должно помочь, я думаю.

• один проход по списку
• хранилище данных - это SortedDictionary (двоичное дерево с балансировкой по высоте), поэтому поиск, вставка и удаление - это O (log N).

Вот код:

public class SummaryData
{
  public SummaryData( int id )
  {
    this.SummaryId   = id ;
    this.TotalNumber = 0  ;
  }
  public int SummaryId   { get; set; }
  public int TotalNumber { get; set; }
}

public class ListItem
{
  public int      Id     ;
  public int      Number ;
  public DateTime Time   ;
}

public IEnumerable<SummaryData> Summarize( IEnumerable<ListItem> ItemList )
{
  const long                        TICKS_PER_QUARTER_HOUR = TimeSpan.TicksPerMinute * 15;
  SortedDictionary<int,SummaryData> summary                = new SortedDictionary<int , SummaryData>();

  foreach ( ListItem item in ItemList )
  {
    long TimeOfDayTicks     = item.Time.TimeOfDay.Ticks;
    bool on15MinuteBoundary = ( 0 == TimeOfDayTicks % TICKS_PER_QUARTER_HOUR ? true : false );

    if ( on15MinuteBoundary )
    {
      int         key      = (int)( TimeOfDayTicks / TICKS_PER_QUARTER_HOUR );
      SummaryData value;
      bool        hasValue = summary.TryGetValue( key , out value );

      if ( !hasValue )
      {
        value = new SummaryData( item.Id );
        summary.Add( value.SummaryId , value ) ;
      }
      value.TotalNumber += item.Number;

    }

  }

  return summary.Values;

}

Answer 5

Что является результатом этого алгоритма? Извиняюсь, если я глупый, что не получил его.

Кажется, что он идентифицирует все элементы в itemList, минутное значение которого делится на 15, затем добавляет его числовое значение в счетчик хода и затем добавляет этот счетчик хода в этот объект Aggregates.

Поскольку я не совсем понимаю типы некоторых из этих объектов, я немного размышляю о том, что на самом деле здесь происходит. Кажется, вы агрегируете один раз с «aggregateData + = item.number», а затем агрегируете СНОВА с «Aggregates.Add (aggregateData)». Вы уверены, что не суммируете эти суммы дважды? Мне даже неясно, пытаетесь ли вы суммировать значения подходящих предметов или составить их список.

Кроме того, определенно не обязательно или не оптимально просматривать весь список из 1 миллиона предметов 24 * 4 раза, но я не могу быть уверен, что правильно, без более ясного понимания цели.

Как указано в других ответах, правильный подход, скорее всего, будет повторять элемент itemList ровно один раз и работать с каждым отдельным элементом, а не повторяться ~ 100 раз и отбрасывать каждый элемент в списке ~ 99 раз (поскольку вы знаете, что это может претендовать только на одну из ~ 100 итераций).