Оптимизация процесса огромного списка <T>в C #

Question

Я работаю над алгоритмом планирования, который генерирует / назначает временные интервалы для списка получателей на основе следующих ограничений:

• Макс. Получателей в минуту
• Макс. Получателейв час

Предположим, что время начала доставки 2018-10-17 9:00, и у нас есть 19 получателей с максимальным значением 5 в минуту и ​​10 в час, поэтому вывод должен быть:

1. 5 Получатели будут назначены на 2018-10-17 9:00 AM
2. 5 Получатели будут назначены на 2018-10-17 9:01 AM
3. 5 Получатели будут назначены на 2018-10-17 10:00 AM
4. 4 Получатели будут назначены на 2018-10-17 10:01 AM

Алгоритм оченьТочно, но способ работает следующим образом:

• Сначала он генерирует список временных интервалов или временных окон, которые точно соответствуют номеру.получателей на основе ограничений, которые я упоминал ранее.
• тогда я перемещаю все, что доступно в списке временных интервалов для каждого набора / группы или получателей.
• в списке времениСлоты Я добавил счетчик, который увеличивается для каждого получателя, добавленного к нему, так что я могу отслеживать нет.каждого получателя, добавленного в каждый временной интервал для соблюдения ограничений Макс. в мин. / час.

Предыдущий процесс, который был упрощен в этом фрагменте кода, - я использую цикл while для итерации, в моемслучай, когда получатели 500K это займет 28 минут, чтобы сделать это!Я пытался использовать Parallel.ForEach, но я не мог понять, как реализовать его в этом случае.

DateTime DeliveryStart = DateTime.Now;
//This list has DateTime: Time-windows  values starting from DeliveryStart to the Max value of the time needed to schedule the Recipients
var listOfTimeSlots = new List<Tuple<DateTime, bool, int>>();
//List of Recipients with Two types of data: DateTime to tell when its scheduled and int value refers to the Recipient's ID
var ListOfRecipients = new List<Tuple<DateTime, int>>();
List<Tuple<int, DateTime>> RecipientsWithTimeSlots= new List<Tuple<int, DateTime>>();
int noOfRecipients = ListOfRecipients.Count;

int Prevhour = 0, _AddedPerHour = 0, Prevday = 0;
// Scheduling restrictions 
int _MaxPerHour = 5400, _MaxPerMinute = 90;
int i = 0;
int indexStart = 0;

// ...
//     ...
//           Code to fill listOfTimeSlots ListOfRecipients with Data

while (noOfRecipients > 0)
{
    var TimeStamp = listOfTimeSlots[i];

    int hour = TimeStamp.Item1.Hour;
    int day = TimeStamp.Item1.Day;

    if (Prevhour == 0)
    {
        Prevhour = hour;
        Prevday = day;
    }
    if (Prevhour != hour)
    {
        Prevhour = hour;
        _AddedPerHour = 0;
    }

    if (_AddedPerHour >= _MaxPerHour)
    {
        var tmpItem = listOfTimeSlots.Where(l => l.Item1.Hour == hour && l.Item1.Day == day).LastOrDefault();
        int indexOfNextItem = listOfTimeSlots.LastIndexOf(tmpItem) + 1;
        i = indexOfNextItem;
        _AddedPerHour = 0;
        continue;
    }
    else
    {
        int endIndex;


        endIndex = _MaxPerMinute > noOfRecipients ? noOfRecipients : _MaxPerMinute;

        if (endIndex > Math.Abs(_AddedPerHour - _MaxPerHour))
            endIndex = Math.Abs(_AddedPerHour - _MaxPerHour);

        var RecipientsToIteratePerMinute = ListOfRecipients.GetRange(indexStart, endIndex);

        foreach (var item in RecipientsToIteratePerMinute)
        {
            RecipientsWithTimeSlots.Add(new Tuple<int, DateTime>(item.Item2, TimeStamp.Item1));
            listOfTimeSlots[i] = new Tuple<DateTime, bool, int>(TimeStamp.Item1, true, listOfTimeSlots[i].Item3 + 1);
            _AddedPerHour++;
        }

        indexStart += endIndex;
        noOfRecipients -= endIndex;
        i++;

    }
}

Я упростил здесь код, чтобы не усложнять его понимание, все, что я хочучтобы ускорить цикл while или заменить его на Parallel.ForEach.

В то время как циклический цикл никогда не упрощается, это то, как это работает точно \

Любая помощь или предложение приветствуются.

Answer 1

Здесь другой подход.Сначала он создает группы идентификаторов, а затем назначает им дату на основе требований.

Во-первых, класс для представления групп (избегайте их кортежей):

public class RecipientGroup
{       
    public RecipientGroup(DateTime scheduledDateTime, IEnumerable<int> recipients)
    {
        ScheduledDateTime= scheduledDateTime;
        Recipients = recipients;
    }

    public DateTime ScheduledDateTime { get; private set; }
    public IEnumerable<int> Recipients { get; private set; }

    public override string ToString()
    {
        return string.Format($"Date: {ScheduledDateTime.ToShortDateString()} {ScheduledDateTime.ToLongTimeString()}, count: {Recipients.Count()}");
    }
}

Затем классперебирать группы.Вы поймете, почему это необходимо позже:

public class GroupIterator
{        
    public GroupIterator(DateTime scheduledDateTime)
    {
        ScheduledDateTime = scheduledDateTime;
    }

    public DateTime ScheduledDateTime { get; set; }
    public int Count { get; set; }
}

Теперь код:

DateTime DeliveryStart = new DateTime(2018, 10, 17);

//List of Recipients (fake populate function)
IEnumerable<int> allRecipients = PopulateRecipients();            

// Scheduling restrictions 
int maxPerMinute = 90;
int maxPerHour = 270;

//Creates groups broken down by the max per minute.  
var groupsPerMinute = allRecipients
        .Select((s, i) => new { Value = s, Index = i })
        .GroupBy(x => x.Index / maxPerMinute)
        .Select(group => group.Select(x => x.Value).ToArray());

//This will be the resulting groups
var deliveryDateGroups = new List<RecipientGroup>();

//Perform an aggregate run on the groups using the iterator
groupsPerMinute.Aggregate(new GroupIterator(DeliveryStart), (iterator, ids) => 
{
    var nextBreak = iterator.Count + ids.Count();
    if (nextBreak >= maxPerHour)
    {
        //Will go over limit, split
        var difference = nextBreak-maxPerHour;
        var groupSize = ids.Count() - difference;
        //This group completes the batch
        var group = new RecipientGroup(iterator.ScheduledDateTime, ids.Take(groupSize));
        deliveryDateGroups.Add(group);
        var newDate = iterator.ScheduledDateTime.AddHours(1).AddMinutes(-iterator.ScheduledDateTime.Minute);
        //Add new group with remaining recipients.
        var stragglers = new RecipientGroup(newDate, ids.Skip(groupSize));
        deliveryDateGroups.Add(stragglers);
        return new GroupIterator(newDate, difference);
    }                    
    else
    {
        var group = new RecipientGroup(iterator.ScheduledDateTime, ids);
        deliveryDateGroups.Add(group);
        iterator.ScheduledDateTime = iterator.ScheduledDateTime.AddMinutes(1);
        iterator.Count += ids.Count();
        return iterator;
    }                      
});

//Output minute group count
Console.WriteLine($"Group count: {deliveryDateGroups.Count}");

//Groups by hour
var byHour = deliveryDateGroups.GroupBy(g => new DateTime(g.ScheduledDateTime.Year, g.ScheduledDateTime.Month, g.ScheduledDateTime.Day, g.ScheduledDateTime.Hour, 0, 0));

Console.WriteLine($"Hour Group count: {byHour.Count()}");
foreach (var group in byHour)
{
     Console.WriteLine($"Date: {group.Key.ToShortDateString()} {group.Key.ToShortTimeString()}; Count: {group.Count()}; Recipients: {group.Sum(g => g.Recipients.Count())}");
}

Вывод:

Количество групп: 5556

Количество часов в группе: 1852

Дата: 17.10.2008, 12:00;Количество: 3;Получатели: 270

Дата: 17.10.2008, 1:00;Количество: 3;Получатели: 270

Дата: 17.10.2008, 2:00;Количество: 3;Получатели: 270

Дата: 17.10.2008 3:00;Количество: 3;Получатели: 270

Дата: 17.10.2008 г. 4:00;Количество: 3;Получатели: 270

Дата: 17.10.2008, 5:00;Количество: 3;Получатели: 270

... и т. Д. Для всех групп 1852.

Это займет около 3 секунд.

Я уверен, что есть крайние случаи,Я написал это в спешке, так что просто подумайте о них.