遇到一个有意思的面试题，在这里留下思路。
题目
给定一个任务队列，然后执行，如果有依赖，就将依赖的结果执行返回，最终得到队列中每个任务的结果并返回。
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 }
解到到这里基本问题是解决了，但是目前的这个方案，存在一些漏洞：
- 如果遇到依赖不存在的情况循环无法终止
- 如果遇到依赖循环的情况，队列循环也无法终止
优化解法一：加入依赖错误检测
思路是如果当前任务在循环中执行了第二次仍失败，那么就可以命定为该任务队列中有错误，需要终止执行，抛出错误。
第一种：假设最后一个任务才是没有依赖的任务，那么正常情况下，最大需要执行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]
}
}
总结
考点掌握：
- 队列
- 递归
- 数组改键值对
- 值存储（类似缓存）
- 错误处理 try-catch
- 扩展运算符
网友评论