c# - 如何使用 LINQ to Objects 安排作业而不重叠？

Question

这是另一个资源分配问题。我的目标是运行一个查询，将任何时隙的最高优先级作业分配给两个 CPU 内核之一(只是一个例子，所以让我们假设没有中断或多任务处理)。注意:这类似于 my earlier post about partitioning , 但关注重叠时间和分配多个项目，而不仅仅是最优先的项目。

这是我们的对象:

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

真实的数据集非常大，但对于这个例子，假设有 1000 个作业要分配给两个 CPU 核心。它们都被加载到内存中，我需要对它们运行一个 LINQ to Objects 查询。目前，这需要将近 8 秒的时间和 140 万次比较。

我利用了 this post 中引用的逻辑确定两个项目是否重叠，但与那个帖子不同，我不仅仅需要找到重叠项目，而是安排任何重叠集合的顶部项目，然后安排下一个项目。

在进入代码之前，让我指出当前低效算法的步骤:

1. 确定剩余的工作(通过删除任何已分配的工作)
2. 通过自连接所有剩余作业并按优先级选择最重叠的作业，将作业分配给当前核心。
3. 通过执行查询连接新作业
4. 从第 1 站开始为每个剩余的核心重复

问题:

• 如何最有效地完成这项工作？
• 可以避免第2步的子查询吗？也许通过分组，但我不确定如何基于 .Overlaps() 扩展方法进行分组。
• 工作已经安排好了。第 2 步能否利用这一事实，并且只与短范围内的项目而不是每个工作进行比较？
• 有没有比循环更有效的分配给核心的方法？这可以避免执行步骤 3 中的查询吗？同样，如果我可以将重叠的作业集分组，那么分配核心就是为每个重叠集选择 N 个简单的问题。

完整示例代码:

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();
    }
}

示例输出:

1000 Jobs x 2 Cores
Populating data
Completed in 0.00ms
Assigning Jobs to Cores
Completed in 7,998.00ms

Jobs:
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

Assignments:
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

Total Comparisons: 1,443,556.00
Any key to continue

Answer 1

是否有理由为此任务使用 linq to object collections？我想我会创建一个事件列表，将所有作业放入队列中，并在事件列表低于 10 时将下一个作业从队列中弹出并将其粘贴到事件列表中。很容易跟踪哪个核心正在执行哪个任务，并将队列中的下一个任务分配给最不忙的核心。将完成的事件连接到作业或仅监视事件列表，您就会知道何时适合将另一个作业从队列中弹出并放入事件列表。