More Efficient Solution For Looping through Array of Objects and Evaluating Dependencies in Each Object

Question

I recently did a code challenge where I needed to write a function that evaluates an array of objects, each object having a dependencies property that contains the id's of other objects in the array. See below.

var task = [
    { "id": 1, "depends": [2, 3] },
    { "id": 2, "depends": [] },
    { "id": 3, "depends": [2, 4] },
    { "id": 4, "depends": [] }
];

The function should loop through the array and "process" each task if their dependencies have been met and then log it. So in the example above, task #1 gets skipped because it depends on tasks #2 and #3. So next comes task #2. It has no dependencies so we can "process" it. Then we move on to three but it is skipped because it depends on task 4 (not yet processed). Then we get to four, process it, then go back and evaluate the remaining tasks. The expected output should look like the below.

Task #2 is complete.
Task #4 is complete.
Task #3 is complete.
Task #1 is complete.

I was able to find a solution but I feel like there can be a more efficient one in terms of time complexity. I found a question that is similar to what I'm looking for but it's a bit different from my case so wasn't as much help as I'd hoped.

My solution is in the snippet. It's a recursive function that loops through the tasks and if their dependencies have been met, put their id in a map. Then use this map to filter an object's dependencies based on whether or not that dependency is in the map.

var task = [
    { "id": 1, "depends": [2, 3] },
    { "id": 2, "depends": [] },
    { "id": 3, "depends": [2, 4] },
    { "id": 4, "depends": [] }
];

var map = {}

const processTasks = (arr) => {
    
    arr.forEach((t, i)=>{
        if (!t.depends.length){
          console.log(`task ${t.id} complete.`)
          map[t.id] = true
          arr.splice(i, 1)
        } else {
          t.depends = t.depends.filter(x=>{
            return !map[x]
          })
        }
    })
  
    if (arr.length > 0){
      processTasks(arr)
    }
}

processTasks(task.sort((a, b)=> a.depends.length < b.depends.length ? -1 : 1))

If the code is working but you're only looking for improvement, this question belongs in codeReview, not StackOverflow — Jeremy Thille
– Jeremy Thille, Commented Jan 24, 2021 at 15:57
I'd suggest that you look up topological sorting for standard approaches to this problem. — Scott Sauyet
– Scott Sauyet, Commented Jan 28, 2021 at 15:24

Andrew Vershinin · Accepted Answer · 2021-01-24 16:05:53Z

2

Your algorithm has O(N^2 + M) - quadratic complexity (N - number of tasks, M - total length of depends arrays).

You need to find an order of tasks so that if task A precedes task B, then A doesn't depend on B. This process is called topological sorting. After performing that sorting, you can execute tasks in this order in one traversal - O(N). The sorting itself has O(N + M) time complexity, so the whole process will be O(N + M) - much faster.

edited Jan 24, 2021 at 16:05

answered Jan 24, 2021 at 15:58

Andrew Vershinin

1,97813 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

lissettdm · Accepted Answer · 2021-02-02 12:05:02Z

1

You can use Pub/Sub to get notified when the task is complete. This way you don't need to order the tasks, just listen when a task is completed:

function TaskManager() {
  let listeners = {};

  function listener(taskId, callback) {
    listeners[taskId] = listeners[taskId] || [];
    listeners[taskId].push(callback);
  }

  function dispatch(taskId) {
    listeners[taskId].forEach(callback => callback(taskId));
  }

  return {
    listener,
    dispatch
  };
}

const tasks = [{ id: 1, depends: [2, 3] },{ id: 2, depends: [] },{ id: 3, depends: [2, 4] },{ id: 4, depends: [] }];

let taskManager = new TaskManager();

let taskdepends = {};

function checkStatus(id) {
  let isReady = false;
  if (!taskdepends[id].length) {
    console.log(`task ${id} complete.`);
    taskManager.dispatch(id);
    isReady = true;
  }
  return isReady;
}

function createListeners() {
  tasks.forEach(task => {
    const id = task.id;
    taskdepends[id] = task.depends;

    function onDependCompleted(dep) {
      taskdepends[id] = taskdepends[id].filter(d => d !== dep);
      checkStatus(id);
    }

    taskdepends[id].forEach(d => {
      taskManager.listener(d, onDependCompleted);
    });
  });
}

const run = () => {
  createListeners(); //--> create listener for task's dependencies
  tasks.forEach(task => checkStatus(task.id));
};

run();

You can improve it adding a function to remove the event listeners and check for circular dependencies.

edited Feb 2, 2021 at 12:05

answered Jan 24, 2021 at 17:53

lissettdm

13.2k1 gold badge25 silver badges43 bronze badges

3 Comments

Matt Croak Over a year ago

I like the async logic but in terms of time complexity how is it better than my original solution? It looks like it's still using recursion and loop within the recursive call. Can you elaborate more?

lissettdm Over a year ago

@MattCroak I updated my answer with another solution. I think the second approach is much better

lissettdm Over a year ago

I removed the async part, I think the pub/sub solution is enough, also you can run the listener async.

CertainPerformance · Accepted Answer · 2021-01-27 19:41:39Z

0

Sorting the array every time something changes is wasteful. I think a better approach would be to first put all tasks into a collection indexed by the depends that it has. For example, the { "id": 1, "depends": [2, 3] } can be put into the collection at index 2 and at index 3. Then, once the collection is constructed, iterate over all initial tasks with no dependencies and run them. Whenever a task is run, look up the task's ID in the collection and remove the task ID from each dependent task's depends array. If the array ends up empty, that task can be run.

var tasks = [
    { "id": 1, "depends": [2, 3] },
    { "id": 2, "depends": [] },
    { "id": 3, "depends": [2, 4] },
    { "id": 4, "depends": [] }
];

const runTask = task => {
  const { id } = task;
  console.log(`task ${id} complete.`);
  if (!tasksByDependID[id]) return;
  for (const dependTask of tasksByDependID[id]) {
    dependTask.depends.delete(id);
    if (!dependTask.depends.size) runTask(dependTask);
  }
};
const tasksByDependID = {};
const initialTasks = [];
for (const task of tasks) {
  if (!task.depends.length) initialTasks.push(task);
  const taskWithSet = { id: task.id, depends: new Set(task.depends) };
  for (const id of task.depends) {
    tasksByDependID[id] = tasksByDependID[id] || [];
    tasksByDependID[id].push(taskWithSet);
  }
}
initialTasks.forEach(runTask);

edited Jan 27, 2021 at 19:41

answered Jan 24, 2021 at 16:11

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

1 Comment

Matt Croak Over a year ago

Other than filtering on each loop (I edited the code to filter before the processTasks function is called), I'm curious how this is more efficient in terms of time complexity considering it still uses recursion and a loop within the recursive function. Can you elaborate more on the time complexity?

Collectives™ on Stack Overflow

More Efficient Solution For Looping through Array of Objects and Evaluating Dependencies in Each Object

3 Answers 3

Comments

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related