遇到一個有意思的面試題，在這里留下思路。
題目
給定一個任務(wù)隊列，然后執(zhí)行，如果有依賴，就將依賴的結(jié)果執(zhí)行返回，最終得到隊列中每個任務(wù)的結(jié)果并返回。
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應(yīng)該為：
{ task1: 3, task2: 12, task3: 8, task4: 18 }
*/
});
解法一：遇到?jīng)]有值的依賴，放入隊尾等待執(zhí)行
思考：
1. 循環(huán)隊列，執(zhí)行任務(wù)（每次執(zhí)行任務(wù)，先將隊頭任務(wù)彈出執(zhí)行）
2. 依賴檢查
- 待執(zhí)行的任務(wù)檢查依賴如果遇到?jīng)]有依賴的直接返回結(jié)果，并將結(jié)果保存
- 遇到有依賴的，遍歷依賴先從結(jié)果中匹配看是否有已經(jīng)算出的結(jié)果，如果沒有匹配到執(zhí)行優(yōu)先級繞后
- 遍歷依賴完成判斷結(jié)果數(shù)組是否和依賴數(shù)組長度一樣（每一個依賴都拿到的結(jié)果），執(zhí)行結(jié)果保存
3. 循環(huán)上面的情況，直到隊列中沒有任務(wù)即可
4. 錯誤處理，如果上面執(zhí)行代碼出問題，返回err
代碼
function runAllTask(list, cb) {
// 創(chuàng)建結(jié)果數(shù)組
let obj = {}
// 錯誤處理
try {
// 循環(huán)執(zhí)行任務(wù)
while(list.length > 0) {
// 彈出要執(zhí)行的任務(wù)
let task = list.shift();
// 依賴判斷
if (!task.deps.length) {
obj[task.id] = task.runTask()
} else {
// 有依賴，創(chuàng)建依賴結(jié)果數(shù)組
let arr = []
task.deps.every(val => {
// 有結(jié)果直接放入，繼續(xù)循環(huán)
if (obj[val] !== undefined) {
arr.push(obj[val])
return true
// 無結(jié)果說明依賴內(nèi)容沒執(zhí)行，放入隊尾等待執(zhí)行，循環(huán)結(jié)束
} else {
list.push(task);
return false
}
})
// 判斷依賴是否全部執(zhí)行完畢
if (arr.length === task.deps.length) {
obj[task.id] = task.runTask(...arr)
}
}
}
// 返回結(jié)果
cb(null, obj);
} catch(e) {
cb(e, null);
}
}
// 執(zhí)行結(jié)果
// { task1: 3, task3: 8, task2: 12, task4: 18 }
解到到這里基本問題是解決了，但是目前的這個方案，存在一些漏洞：
- 如果遇到依賴不存在的情況循環(huán)無法終止
- 如果遇到依賴循環(huán)的情況，隊列循環(huán)也無法終止
優(yōu)化解法一：加入依賴錯誤檢測
思路是如果當前任務(wù)在循環(huán)中執(zhí)行了第二次仍失敗，那么就可以命定為該任務(wù)隊列中有錯誤，需要終止執(zhí)行，拋出錯誤。
第一種：假設(shè)最后一個任務(wù)才是沒有依賴的任務(wù)，那么正常情況下，最大需要執(zhí)行l(wèi)ength的階乘，如果進入循環(huán)都判斷不能超過這個次數(shù)也是可以解決，但是這樣性能消耗太大，有很多不必要的循環(huán)次數(shù)。
第二種：在當前執(zhí)行的任務(wù)中，要記錄一下上一個成功執(zhí)行的任務(wù)名稱是什么，如果上一次成功執(zhí)行的名稱一樣，那么就判定進入到了死循環(huán)。
function runAllTask(list, cb) {
let obj = {}
// 記錄一下上一個運行的id，避免沒有匹配的task出現(xiàn)
let last_task = null;
try {
// 如果都運行完，就有了結(jié)果
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中有結(jié)果直接獲取，沒有結(jié)果返回到隊尾
task.deps.every(val => {
// 如果運行成功的上一個和當前一樣，表示一個任務(wù)執(zhí)行了兩次，避免陷入死循環(huán)
if (task.last_task === last_task) throw new Error('no match')
if (obj[val] !== undefined) {
arr.push(obj[val])
return true
} else {
//將上一次成功的任務(wù)id記錄到當前任務(wù)中
task.last_task = last_task
list.push(task);
return false
}
})
// 如果當前長度和任務(wù)依賴長度一樣，說明執(zhí)行成功
if (arr.length === task.deps.length) {
// 將參數(shù)打散
obj[task.id] = task.runTask(...arr)
// 記錄成功的任務(wù)id
last_task = task.id
}
}
}
// 返回成功的結(jié)果
cb(null, obj);
} catch(e) {
// 返回錯誤的結(jié)果
cb(e, null);
}
}
這個方案解決了一些依賴錯誤導(dǎo)致的無法終止的問題，不過存在一些漏洞：
有問題的任務(wù)，還是循環(huán)了兩三次以上，不必要的性能浪費
解法二：遞歸調(diào)用
如果不移動到隊尾，直接遞歸調(diào)用依賴返回結(jié)果，這樣就完美解決了上面的問題。
function runAllTask(list, cb) {
// 數(shù)組改鍵值對(為了定義遞歸函數(shù)的時候，不用每次遍歷數(shù)組)
let listObj = {}
// 結(jié)果數(shù)組
let obj = {}
try {
// 數(shù)組改鍵值對
list.forEach(val => {
listObj[val.id] = val
})
// 遍歷執(zhí)行任務(wù)
list.forEach(val => {
runOneTask(val.id)
})
// 成功返回obj
cb(null, obj)
} catch(e) {
cb(e, null)
}
// 執(zhí)行單個任務(wù)
function runOneTask(name) {
// 如果結(jié)果里面有，直接讀取結(jié)果，使用緩存
if(obj[name]) return obj[name]
// 當前依賴數(shù)組結(jié)果
let depResult = [];
// 遍歷依賴
listObj[name].deps.forEach(dep => {
// 每個依賴遞歸執(zhí)行結(jié)果
depResult.push(runOneTask(dep))
})
// 將結(jié)果執(zhí)行加到結(jié)果對象中
obj[name] = listObj[name].runTask(...depResult)
// 返回結(jié)果
return obj[name]
}
}
總結(jié)
考點掌握：
- 隊列
- 遞歸
- 數(shù)組改鍵值對
- 值存儲（類似緩存）
- 錯誤處理 try-catch
- 擴展運算符
