I have a list of tasks and all these tasks need to be executed only after all the dependencies are resolved for each task. I am struggling to figure out a way to finish running all the tasks in optimal time.
// Each node is a async job, illustrated by setTimeout.
// A and C can run at the same time.
// D, needs to wait for A and C to be done.
// E needs to wait for A and D to be done.
function runTasks(tasks) {
// run tasks
}
// Sample of tasks
var tasks = {
'a': {
job: function (finish) {
setTimeout(function () {
console.log('a done');
finish();
}, 500);
},
},
'c': {
job: function (finish) {
setTimeout(function () {
console.log('c done');
finish();
}, 200);
},
dependencies: [],
},
'd': {
job: function (finish) {
setTimeout(function () {
console.log('d done');
finish();
}, 100);
},
dependencies: ['a','c'],
},
'e': {
job: function (finish) {
setTimeout(function () {
console.log('e done');
finish();
}, 200);
},
dependencies: ['a', 'd'],
},
};
CodePudding user response：
Something like this might be possible, I have changed the jobs to async methods and I keep track of them being resolved or not.
This code does not check for errors within the job or for circular dependencies.
Output of the script:
b done
a done
c done
e done
done
Code:
const runTasks = async tasks => {
const taskArray = Object.entries(tasks)
const resolved = {}
while (taskArray.length) {
const tasksToExecute = []
for (const task of taskArray) {
const dependencies = task[1].dependencies || []
if (dependencies.length === 0 || dependencies.every(dependency => resolved[dependency] || false)) {
tasksToExecute.push(task)
}
}
await Promise.all(tasksToExecute.map(t => t[1].job()))
tasksToExecute.forEach(t => {
resolved[t[0]] = true
taskArray.splice(taskArray.indexOf(t[0]), 1)
})
}
}
const tasks = {
a: {
job: async function () {
return new Promise(resolve => {
setTimeout(() => {
console.log("a done")
resolve()
}, 500)
})
},
},
c: {
job: async function () {
return new Promise(resolve => {
setTimeout(() => {
console.log("c done")
resolve()
}, 200)
})
},
dependencies: ["a", "b"],
},
b: {
job: async function () {
return new Promise(resolve => {
setTimeout(() => {
console.log("b done")
resolve()
}, 100)
})
},
dependencies: [],
},
e: {
job: async function () {
return new Promise(resolve => {
setTimeout(() => {
console.log("e done")
resolve()
}, 200)
})
},
dependencies: ["c", "b"],
},
}
runTasks(tasks).then(r => console.log("done"))
CodePudding user response：
A simple recursive dependencies evaluation with caching of results will do. Use Promise.all to wait for all dependencies:
function runTasks(tasks) {
const promises = {};
function runTask(name) {
const {dependencies, job} = tasks[name];
return promises[name] ??= Promise.all(dependencies.map(runTask)).then(job);
}
return Promise.all(Object.keys(tasks).map(runTask));
}
Maybe use Promise.allSettled instead of Promise.all in the final return statement.
If you need to detect circular dependencies, you can use
…
const circular = Promise.reject(new Error("circular dependency"));
circular.catch(() => { /* ignore */ }); // prevent unhandled rejection
function runTask(name) {
const {dependencies, job} = tasks[name];
if (promises[name] != null) return promises[name];
promises[name] = circular;
return promises[name] = Promise.all(dependencies.map(runTask)).then(job);
}
…
CodePudding user response：
You can start parallel promises which can be started.
- Start all independent task first which has no dependencies
- After completing independent tasks store in map/set
- Then filter a new set of tasks using the complete set repeat steps.
const wait = (ms, task) =>
new Promise((resolve) =>
setTimeout(() => {
console.log(`${task} done`);
resolve();
}, ms)
);
const tasks = {
a: {
job: () => wait(500, "A"),
dependencies: [],
},
c: {
job: () => wait(500, "C"),
dependencies: [],
},
d: {
job: () => wait(500, "D"),
dependencies: ["a", "c"],
},
e: {
job: () => wait(500, "E"),
dependencies: ["a", "d"],
},
};
const run = async () => {
const completed = new Set();
const keys = Object.keys(tasks);
const runTasks = async (pendingTasks) => {
const promises = pendingTasks.map((key) => tasks[key].job());
await Promise.all(promises);
pendingTasks.forEach((key) => completed.add(key));
};
const runner = async () => {
const pendingTasks = keys.filter((key) => {
if (!completed.has(key)) {
const { dependencies } = tasks[key];
return dependencies.every((dependency) => completed.has(dependency));
}
return false;
});
if (pendingTasks.length !== 0) {
await runTasks(pendingTasks);
return runner();
}
};
await runner();
};
run();CodePudding user response：
This uses Promise.race to treat tasks independently of others. Using Promise.all is not optimal as it wait for all dependent tasks to complete before evaluating if another task can be started.
I think this is optimal timewise. It might have higher processing overhead as all jobs are kept in a single object and might be better handled by moving jobs to a completed object to avoid reevaluating already completed tasks.
NB: This doesn't evaluate circular dependencies or that indeed, dependencies are tasks.
"use strict";
class Job {
constructor(getJobs, name, task) {
this.getJobs = getJobs;
this.name = name;
this.task = task;
}
isWaiting() {
return this.promise !== undefined;
}
isComplete() {
return 'result' in this;
}
isBlocked() {
return !(this.task.dependencies || []).map(name => this.getJobs()[name]).every(job => job.isComplete()) || false;
}
isElligible() {
return !this.isWaiting() && !this.isComplete() && !this.isBlocked();
}
}
async function runTasks(tasks) {
const jobs = Object.entries(tasks)
.reduce((acc, [name, task]) => {
acc[name] = new Job(() => jobs, name, task);
return acc;
}, {});
while (true) {
Object.keys(jobs).forEach(name => {
if (jobs[name].isElligible()) {
console.log(`${name} elligible`);
jobs[name].promise = new Promise(resolve => {
console.log(`${name} starting`);
jobs[name].task.job(resolve);
}).then(res => {
jobs[name].result = res;
delete jobs[name].promise;
});
}
});
const pending = Object.values(jobs).filter(job => job.isWaiting());
console.log('racing', pending.map(j => j.name));
if (pending.length) {
await Promise.race(pending.map(job => job.promise));
}
else {
break;
}
}
}
var tasks = {
'a': {
job: function (finish) {
setTimeout(function () {
console.log('a done');
finish();
}, 500);
},
},
'c': {
job: function (finish) {
setTimeout(function () {
console.log('c done');
finish();
}, 200);
},
dependencies: [],
},
'd': {
job: function (finish) {
setTimeout(function () {
console.log('d done');
finish();
}, 100);
},
dependencies: ['a', 'c'],
},
'e': {
job: function (finish) {
setTimeout(function () {
console.log('e done');
finish();
}, 200);
},
dependencies: ['a', 'd'],
},
'f': {
job: function (finish) {
setTimeout(function () {
console.log('f done');
finish();
}, 500);
},
dependencies: ['c'],
},
};
runTasks(tasks).then(() => console.log('ALL done'));