Este es otro problema de asignación de recursos. Mi objetivo es ejecutar una consulta para asignar el trabajo de máxima prioridad para cualquier intervalo de tiempo a uno de los dos núcleos de la CPU (solo un ejemplo, así que supongamos que no hay interrupciones ni tareas múltiples). Nota: esto es similar amy publicación anterior sobre particiones, pero se centra en la superposición de tiempos y la asignación de varios elementos, no solo el elemento de máxima prioridad.

Aquí está nuestro objeto:

public class Job
{
    public int Id;
    public int Priority;
    public DateTime Begin;
    public DateTime End;
}

El conjunto de datos real es muy grande, pero para este ejemplo, supongamos que hay 1000 trabajos para asignar a dos núcleos de CPU. Todos están cargados en la memoria, y necesito ejecutar una sola consulta LINQ to Objects contra ellos. Actualmente, esto lleva casi 8 segundos y 1.4 millones de comparaciones.

He aprovechado la lógica citada enesta publicació para determinar si dos elementos se superponen, pero a diferencia de esa publicación, no solo necesito encontrar elementos superpuestos, sino programar el elemento superior de cualquier conjunto superpuesto y luego programar el siguiente.

Antes de llegar al código, permítanme señalar los pasos del algoritmo actual ineficiente:

Determine los trabajos restantes (eliminando los ya asignados) Asigne trabajos al núcleo actual uniéndose a todos los trabajos restantes y seleccionando el trabajo superpuesto superior por prioridad.Concatene los nuevos trabajos ejecutando la consultaRepetir comenzando en la Parada 1 para cada núcleo restante

Preguntas:

¿Cómo se puede hacer esto de manera más eficiente? ¿Puedo evitar la subconsulta en el paso 2? Quizás agrupando, pero no estoy seguro de cómo puedo agrupar según el método de extensión .Overlaps (). Los trabajos ya están ordenados. ¿Puede el paso 2 aprovechar ese hecho y solo compararlo con artículos dentro de un rango corto en lugar de cada trabajo? ¿Hay alguna forma más eficiente de asignar a núcleos en lugar de bucle? ¿Esto podría evitar ejecutar la consulta en el Paso 3? Nuevamente, si pudiera agrupar conjuntos de trabajos superpuestos, la asignación de núcleos es simplemente una cuestión de seleccionar N por conjunto superpuesto.

Código de muestra completo:

public class Job
{
    public static long Iterations;

    public int Id;
    public int Priority;
    public DateTime Begin;
    public DateTime End;

    public bool Overlaps(Job other)
    {
        Iterations++;
        return this.End > other.Begin && this.Begin < other.End;
    }
}

public class Assignment
{
    public Job Job;
    public int Core;
}

class Program
{
    static void Main(string[] args)
    {
        const int Jobs = 1000;
        const int Cores = 2;
        const int ConcurrentJobs = Cores + 1;
        const int Priorities = Cores + 3;
        DateTime startTime = new DateTime(2011, 3, 1, 0, 0, 0, 0);
        Console.WriteLine(string.Format("{0} Jobs x {1} Cores", Jobs, Cores));
        var timer = Stopwatch.StartNew();

        Console.WriteLine("Populating data");
        var jobs = new List<Job>();
        for (int jobId = 0; jobId < Jobs; jobId++)
        {
            var jobStart = startTime.AddHours(jobId / ConcurrentJobs).AddMinutes(jobId % ConcurrentJobs);
            jobs.Add(new Job() { Id = jobId, Priority = jobId % Priorities, Begin = jobStart, End = jobStart.AddHours(0.5) });
        }
        Console.WriteLine(string.Format("Completed in {0:n}ms", timer.ElapsedMilliseconds));
        timer.Restart();

        Console.WriteLine("Assigning Jobs to Cores");
        IEnumerable<Assignment> assignments = null;
        for (int core = 0; core < Cores; core++)
        {
            // avoid modified closures by creating local variables
            int localCore = core;
            var localAssignments = assignments;

            // Step 1: Determine the remaining jobs
            var remainingJobs = localAssignments == null ? 
                                                jobs :
                                                from j in jobs where !(from a in localAssignments select a.Job).Contains(j) select j;

            // Step 2: Assign the top priority job in any time-slot to the core
            var assignmentsForCore = from s1 in remainingJobs
                              where
                                  (from s2 in remainingJobs
                                   where s1.Overlaps(s2)
                                   orderby s2.Priority
                                   select s2).First().Equals(s1)
                              select new Assignment { Job = s1, Core = localCore };

            // Step 3: Accumulate the results (unfortunately requires a .ToList() to avoid massive over-joins)
            assignments = assignments == null ? assignmentsForCore.ToList() : assignments.Concat(assignmentsForCore.ToList());
        }

        // This is where I'd like to Execute the query one single time across all cores, but have to do intermediate steps to avoid massive-over-joins
        assignments = assignments.ToList();

        Console.WriteLine(string.Format("Completed in {0:n}ms", timer.ElapsedMilliseconds));
        Console.WriteLine("\nJobs:");
        foreach (var job in jobs.Take(20))
        {
            Console.WriteLine(string.Format("{0}-{1} Id {2} P{3}", job.Begin, job.End, job.Id, job.Priority));
        }

        Console.WriteLine("\nAssignments:");
        foreach (var assignment in assignments.OrderBy(a => a.Job.Begin).Take(10))
        {
            Console.WriteLine(string.Format("{0}-{1} Id {2} P{3} C{4}", assignment.Job.Begin, assignment.Job.End, assignment.Job.Id, assignment.Job.Priority, assignment.Core));
        }

        Console.WriteLine(string.Format("\nTotal Comparisons: {0:n}", Job.Iterations));

        Console.WriteLine("Any key to continue");
        Console.ReadKey();
    }
}

Salida de muestra:

1000 empleos x 2 núcleos
Populación de datos
Completado en 0.00ms
Asignación de trabajos a núcleos
Completado en 7,998.00ms

Trabajos
3/1/2011 12:00:00 AM-3/1/2011 12:30:00 AM Id 0 P0
3/1/2011 12:01:00 AM-3/1/2011 12:31:00 AM Id 1 P1
3/1/2011 12:02:00 AM-3/1/2011 12:32:00 AM Id 2 P2
3/1/2011 1:00:00 AM-3/1/2011 1:30:00 AM Id 3 P3
3/1/2011 1:01:00 AM-3/1/2011 1:31:00 AM Id 4 P4
3/1/2011 1:02:00 AM-3/1/2011 1:32:00 AM Id 5 P0
3/1/2011 2:00:00 AM-3/1/2011 2:30:00 AM Id 6 P1
3/1/2011 2:01:00 AM-3/1/2011 2:31:00 AM Id 7 P2
3/1/2011 2:02:00 AM-3/1/2011 2:32:00 AM Id 8 P3
3/1/2011 3:00:00 AM-3/1/2011 3:30:00 AM Id 9 P4
3/1/2011 3:01:00 AM-3/1/2011 3:31:00 AM Id 10 P0
3/1/2011 3:02:00 AM-3/1/2011 3:32:00 AM Id 11 P1
3/1/2011 4:00:00 AM-3/1/2011 4:30:00 AM Id 12 P2
3/1/2011 4:01:00 AM-3/1/2011 4:31:00 AM Id 13 P3
3/1/2011 4:02:00 AM-3/1/2011 4:32:00 AM Id 14 P4
3/1/2011 5:00:00 AM-3/1/2011 5:30:00 AM Id 15 P0
3/1/2011 5:01:00 AM-3/1/2011 5:31:00 AM Id 16 P1
3/1/2011 5:02:00 AM-3/1/2011 5:32:00 AM Id 17 P2
3/1/2011 6:00:00 AM-3/1/2011 6:30:00 AM Id 18 P3
3/1/2011 6:01:00 AM-3/1/2011 6:31:00 AM Id 19 P4

Asignaciones:
3/1/2011 12:00:00 AM-3/1/2011 12:30:00 AM Id 0 P0 C0
3/1/2011 12:01:00 AM-3/1/2011 12:31:00 AM Id 1 P1 C1
3/1/2011 1:00:00 AM-3/1/2011 1:30:00 AM Id 3 P3 C1
3/1/2011 1:02:00 AM-3/1/2011 1:32:00 AM Id 5 P0 C0
3/1/2011 2:00:00 AM-3/1/2011 2:30:00 AM Id 6 P1 C0
3/1/2011 2:01:00 AM-3/1/2011 2:31:00 AM Id 7 P2 C1
3/1/2011 3:01:00 AM-3/1/2011 3:31:00 AM Id 10 P0 C0
3/1/2011 3:02:00 AM-3/1/2011 3:32:00 AM Id 11 P1 C1
3/1/2011 4:00:00 AM-3/1/2011 4:30:00 AM Id 12 P2 C0
3/1/2011 4:01:00 AM-3/1/2011 4:31:00 AM Id 13 P3 C1
3/1/2011 5:00:00 AM-3/1/2011 5:30:00 AM Id 15 P0 C0

Comparaciones totales: 1,443,556.00
Cualquier tecla para continuar