If you've read my posts and comments you'll know I'm anti-recursion. :) Recursion is always slower, and it always blows up once the data starts getting large. I do enjoy blowing up recursive functions though LOL
Yours explodes on my machine (will vary by many factors) before 8000 task items.
My iterative will go on for as large of a dataset as you want.
My iterative also clocked 25% faster. So for every 10 hours of CPU your recursive uses, mine will use 7.5 hours. That's 2.5 hours of saved CPU time we can buy beer with. :)
Here's the code....
/** @func given a list of tasks, some of which depend on others - get the set of tasks to complete the job - returns an ordered list of all the tasks to do @firstbasecase the last task to start traversing backwards from, to the root node @lastbasecase the task with an empty depends key (root node) @typedef {{task: string, depends: string[]}} taskObj @param {taskObj[]} a tasks @param {string[]} subset @return {string[]} tasks in order to do */constgetTasks=(a,subset)=>{constf=[];//final outputconstleafTask=a.find(o2=>o2.task===subset[subset.length-1]);//first basecasef.push(leafTask.task);letp=leafTask.depends[0];//preceding id. previous dependencywhile(true){consto=a.find(o2=>o2.task===p);p=o.depends[0];f.push(o.task);if(o.depends.length===0){//last basecasereturnf.reverse();}}};//@perftestconstobjs=genObjs(1e4);shuffleElemsDurstenfeldMut(objs);timeInLoop("getTasks",1,()=>getTasks(objs,["9999"]));
P.S. Keep the great posts coming!
P.S.S. If you want the perftest code, let me know. I also did some adjustment to your recursive func.
Yeah, I did worry that my recursive approach would blow up when it comes to huge datasets lol. Again, thanks so much for testing it out and for sharing such a well-organized, readable code snippet :)
Nice work Annie!
If you've read my posts and comments you'll know I'm anti-recursion. :)
Recursion is always slower, and it always blows up once the data starts getting large.
I do enjoy blowing up recursive functions though LOL
Yours explodes on my machine (will vary by many factors) before 8000 task items.
My iterative will go on for as large of a dataset as you want.
My iterative also clocked 25% faster. So for every 10 hours of CPU your recursive uses, mine will use 7.5 hours. That's 2.5 hours of saved CPU time we can buy beer with. :)
Here's the code....
P.S.
Keep the great posts coming!
P.S.S.
If you want the perftest code, let me know.
I also did some adjustment to your recursive func.
Yeah, I did worry that my recursive approach would blow up when it comes to huge datasets lol. Again, thanks so much for testing it out and for sharing such a well-organized, readable code snippet :)
l think you are confusing a couple of fundamental things.
Iteration is generally recursive.
Recursion does not require function calls.
Implementing backtracking via a task list doesn't make something less recursive.
I think you may be conflating recursion with function calls.
Also I suggest considering the cost of all of those linear searches you're doing, as the number of tasks increases.