c# - 事件的最佳执行

Question

假设我有事件或任务

1. 应该全部执行。
2. 没有预先确定的时间，但有些事件比其他事件花费的时间更长
3. 不受 CPU 限制，并受网络/IO 延迟和 transient 错误的影响
4. 依赖他人；在下面的示例中，C 只能执行一次 A 和 B 完成。

用于安排事件以最小化完成所有任务的总时间的最合适算法是什么？我当前的方法不是最优的，因为(在下面的示例中)G 的调度方式会额外增加 20 秒的执行延迟。 this question的答案让我走上了我所在的道路。

这是一个示例(如果它是 DSL)

Task A
{
    Estimation: 10s;
}

Task B
{
    Estimation: 10s;
}

Task C
{
    Estimation: 10s;
    DependsOn A, B;
}

Task D
{
    Estimation: 10s;
    DependsOn C;
}

Task E
{
    Estimation: 10s;
    DependsOn C;
}

Task F
{
    Estimation: 10s;
    DependsOn E, D;
}

Task G
{
    Estimation: 30s;
    DependsOn A, B;
}

这是我所做的(在 C# 中)

创建了事件图(有向无环图)。

以下代码片段来自 TaskManager 类。

private static Graph<ITask> CreateGraph(IEnumerable<ITask> tasks)
{
    if (tasks == null)
        throw new ArgumentNullException(nameof(tasks));

    var nameMap = tasks.ToDictionary(task => task.Id);
    var graph = new Graph<ITask>(nameMap.Values);
    foreach (var task in nameMap.Values)
    {
        foreach (var depdendantTaskName in task.DependsOn)
        {
            var from = nameMap[depdendantTaskName];
            var to = task;
            graph.AddDependency(from, to);
        }
    }
    return graph;
}

执行拓扑排序

public static Node<T>[] Sort<T>(this Graph<T> graph) where T : IComparable
{
    var stack = new Stack<Node<T>>();
    var visited = new HashSet<Node<T>>();

    foreach (var node in graph)
    {
        if (!visited.Contains(node))
        {
            visited.Add(node);
            InternalSort(node, stack, visited);
        }
    }
    return stack.ToArray();
}

private static void InternalSort<T>(Node<T> node, Stack<Node<T>> stack, ISet<Node<T>> visited)
    where T : IComparable
{
    var dependants = node.Dependants;
    foreach (var dependant in dependants)
    {
        if (!visited.Contains(dependant))
        {
            visited.Add(dependant);
            InternalSort(dependant, stack, visited);
        }
    }
    stack.Push(node);
}

这给了我类似 [F,E,D,C,G,B,A] 的东西。如果我使用 dependencies 而不是 dependents，它应该是 [A,B,C,G,D,E,F]。

为每个节点分配一个级别

现在我有了一个排序节点数组，下一步是更新每个节点的级别属性。

public static void Level<T>(this IEnumerable<Node<T>> nodes) where T : IComparable
{
    foreach (var sortedTask in nodes)
    {
        sortedTask.Level = CalculateLevel(sortedTask.Dependencies);
    }
}

public static int CalculateLevel<T>(ICollection<Node<T>> nodes) where T : IComparable
{
    if (nodes.Count <= 0) return 1;
    return nodes.Max(n => n.Level) + 1;
}

这给了我类似 [F:1,G:1,E:2,D:2,C:3,B:4,A:4] 的东西，其中字母是事件名称，数字是级别.如果我反过来这样做，它看起来会像 [F:4,E:3,D:3,G:2,C:2,B:1,A:1]。

小组任务

public static SortedDictionary<int, ISet<T>> Group<T>(this IEnumerable<Node<T>> nodes) where T : IComparable
{
    var taskGroups = new SortedDictionary<int, ISet<T>>();
    foreach (var sortedNode in nodes)
    {
        var key = sortedNode.Level;
        if (!taskGroups.ContainsKey(key))
        {
            taskGroups[key] = new SortedSet<T>();
        }
        taskGroups[key].Add(sortedNode.Value);
    }
    return taskGroups;
}

执行任务

以下遍历每个“级别”并执行任务。

private async Task ExecuteAsync(IDictionary<int, ISet<ITask>> groups, ITaskContext context,
    CancellationToken cancellationToken)
{
    var keys = groups.Keys.OrderByDescending(i => i);
    foreach (var key in keys)
    {
        var tasks = groups[key];
        await Task.WhenAll(tasks.Select(task => task.ExecuteAsync(context, cancellationToken)));   
    }
}

如果任务从最依赖节点到最不依赖节点排序(F 第一，A 或 B最后)

问题

虽然这种方法仍然比顺序方法执行得更快，但无论我如何处理它，总有一些事情在等待 G 完成。如果G与C组合在一起，那么D和E即使不依赖也会延迟20s在 G 上。

如果我反转排序(并调整代码)，G 仅在 F 开始执行时才开始执行。

Answer 1

既然你说(在评论中)可以同时执行的任务数量没有限制，那么有一个简单的解决方案:

1. 为每个任务 i 设置 taskState[i] = UNSTARTED。
2. 对于每个没有剩余依赖项(即空 DependsOn 列表)且尚未启动(即 taskState[i] == UNSTARTED)的任务 i (注意有时可能没有这样的任务):
   • 开始任务。
   • 设置 taskState[i] = RUNNING。
3. 如果当前没有正在运行的任务，则停止——要么您已完成所有任务，要么存在循环依赖。 (您可以通过检查是否有任何任务 i 满足 taskState[i] == UNSTARTED 来判断是哪一个。)
4. 等待任何正在运行的任务完成。让这成为任务 i。
5. 设置 taskState[i] = FINISHED。
6. 遍历所有尚未开始的任务，从每个此类任务的 DependsOn 列表中删除任务 i(如果存在)。
7. 转到 2。