面试题：控制依赖任务执行

遇到一个有意思的面试题，在这里留下思路。

题目

给定一个任务队列，然后执行，如果有依赖，就将依赖的结果执行返回，最终得到队列中每个任务的结果并返回。

const input = [
    {
        id: 'task1',
        deps: [],
        runTask: () => 3,
    },
    {
        id: 'task2',
        deps: ['task1','task3'],
        runTask: (res1, res3) => 1 + res1 + res3,
    },
    {
        id: 'task3',
        deps: ['task1'],
        runTask: (res1) => 5 + res1,
    },
    {
        id: 'task4',
        deps: ['task1', 'task2'],
        runTask: (res1, res2) => 3 + res1 + res2,
    },
];

function runAllTask(list, cb) {
    // TODO
}

runAllTask(input, (err, res) => {
    console.log(err);
    console.log(res);
    /** 
        res应该为：
        { task1: 3, task2: 12, task3: 8, task4: 18 }
    */
});

解法一：遇到没有值的依赖，放入队尾等待执行

思考：

1. 循环队列，执行任务（每次执行任务，先将队头任务弹出执行）
2. 依赖检查
    - 待执行的任务检查依赖如果遇到没有依赖的直接返回结果，并将结果保存
    - 遇到有依赖的，遍历依赖先从结果中匹配看是否有已经算出的结果，如果没有匹配到执行优先级绕后
    - 遍历依赖完成判断结果数组是否和依赖数组长度一样（每一个依赖都拿到的结果），执行结果保存
3. 循环上面的情况，直到队列中没有任务即可
4. 错误处理，如果上面执行代码出问题，返回err

代码

function runAllTask(list, cb) {
    // 创建结果数组
    let obj = {}
    // 错误处理
    try {
        // 循环执行任务
        while(list.length > 0) {
            // 弹出要执行的任务
            let task = list.shift();
            // 依赖判断
            if (!task.deps.length) {
                obj[task.id] = task.runTask()
            } else {
                // 有依赖，创建依赖结果数组
                let arr = []
                task.deps.every(val => {
                    // 有结果直接放入，继续循环
                    if (obj[val] !== undefined) {
                        arr.push(obj[val])
                        return true
                    // 无结果说明依赖内容没执行，放入队尾等待执行，循环结束
                    } else {
                        list.push(task);
                        return false
                    }
                })
                // 判断依赖是否全部执行完毕
                if (arr.length === task.deps.length) {
                    obj[task.id] = task.runTask(...arr)
                }
            }
        }
        // 返回结果
        cb(null, obj);
    } catch(e) {
        cb(e, null);
    }
}

// 执行结果
// { task1: 3, task3: 8, task2: 12, task4: 18 }

解到到这里基本问题是解决了，但是目前的这个方案，存在一些漏洞：

1. 如果遇到依赖不存在的情况循环无法终止
2. 如果遇到依赖循环的情况，队列循环也无法终止

优化解法一：加入依赖错误检测

思路是如果当前任务在循环中执行了第二次仍失败，那么就可以命定为该任务队列中有错误，需要终止执行，抛出错误。

第一种：假设最后一个任务才是没有依赖的任务，那么正常情况下，最大需要执行length的阶乘，如果进入循环都判断不能超过这个次数也是可以解决，但是这样性能消耗太大，有很多不必要的循环次数。

第二种：在当前执行的任务中，要记录一下上一个成功执行的任务名称是什么，如果上一次成功执行的名称一样，那么就判定进入到了死循环。

function runAllTask(list, cb) {
    let obj = {}
    // 记录一下上一个运行的id，避免没有匹配的task出现
    let last_task = null;
    try {
        // 如果都运行完，就有了结果
        while(list.length > 0) {
            let task = list.shift();
            if (!task.deps.length) {
                obj[task.id] = task.runTask()
                // 记录一下当前的task名称
                last_task = task.id
            } else {
                let arr = []
                // 遍历依赖，如果obj中有结果直接获取，没有结果返回到队尾
                task.deps.every(val => {
                    // 如果运行成功的上一个和当前一样，表示一个任务执行了两次，避免陷入死循环
                    if (task.last_task === last_task) throw new Error('no match')
                    if (obj[val] !== undefined) {
                        arr.push(obj[val])
                        return true
                    } else {
                        //将上一次成功的任务id记录到当前任务中
                        task.last_task = last_task
                        list.push(task);
                        return false
                    }
                })
                // 如果当前长度和任务依赖长度一样，说明执行成功
                if (arr.length === task.deps.length) {
                    // 将参数打散
                    obj[task.id] = task.runTask(...arr)
                    // 记录成功的任务id
                    last_task = task.id
                }
            }
        }
        // 返回成功的结果
        cb(null, obj);
    } catch(e) {
        // 返回错误的结果
        cb(e, null);
    }
}

这个方案解决了一些依赖错误导致的无法终止的问题，不过存在一些漏洞：
有问题的任务，还是循环了两三次以上，不必要的性能浪费

解法二：递归调用

如果不移动到队尾，直接递归调用依赖返回结果，这样就完美解决了上面的问题。

function runAllTask(list, cb) {
    // 数组改键值对(为了定义递归函数的时候，不用每次遍历数组)
    let listObj = {}
    // 结果数组
    let obj = {}
    try {
        // 数组改键值对
        list.forEach(val => {
            listObj[val.id] = val
        })
        // 遍历执行任务
        list.forEach(val => {
            runOneTask(val.id)
        })
        // 成功返回obj
        cb(null, obj)
    } catch(e) {
        cb(e, null)
    }

    // 执行单个任务
    function runOneTask(name) {
        // 如果结果里面有，直接读取结果，使用缓存
        if(obj[name]) return obj[name]
        // 当前依赖数组结果
        let depResult = [];
        // 遍历依赖
        listObj[name].deps.forEach(dep => {
            // 每个依赖递归执行结果
            depResult.push(runOneTask(dep))
        })
        // 将结果执行加到结果对象中
        obj[name] = listObj[name].runTask(...depResult)
        // 返回结果
        return obj[name]
    }
}

总结

考点掌握：

1. 队列
2. 递归
3. 数组改键值对
4. 值存储（类似缓存）
5. 错误处理 try-catch
6. 扩展运算符