CODEWITHSUNDEEP
javascriptarraysalgorithmsortingfiltering
Matt Croak
Matt Croak

Reputation: 2888

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

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))

Upvotes: 0

Views: 259

Answers (3)

lissettdm
lissettdm

Reputation: 13078

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.

Upvotes: 1

CertainPerformance
CertainPerformance

Reputation: 371069

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);

Upvotes: 0

Andrew Vershinin
Andrew Vershinin

Reputation: 1968

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.

Upvotes: 2

Related Questions