Efficient way to delete from an array of objects in JavaScript

Question

frontendtasks = [
                 {"id": 1, "name": "User Deletion", "script": "UserDeletion"},
                 {"id": 2, "name": "User Creation", "script_name": "UserCreation"}
                ]

backendtasks = [
                {"id": 1, "name": "User Deletion", "script": "UserDeletion_V2"}
               ]

I'm trying to delete the entry with id = 1 in frontendtask and push the entry from backendtask with this code.

if (backendtasks != 0) {
    for (updated_task in backendtasks ) {
        for (oldtask in frontendtasks) {
            if (frontendtasks[oldtask].id == backendtasks[updated_task].id) {
                frontendtasks[oldtask] = backendtasks[updated_task]
                delete backendtasks[updated_task];
                break;
            }
        }
    }
    for (new_task in backendtasks) {
        frontendtasks.unshift(backendtasks[new_task])
    }
}

This is really slow and CPU hits 100% in browser with 700 items. Is there any efficient way to implement this?

Note that using `delete` on an array is bad practice as it does not change length of array rather it leaves `undefined` at that index — charlietfl, Dec 05 '20 at 17:28
[Don't use `for…in` enumerations on arrays](https://stackoverflow.com/q/500504/1048572), and [don't use the `delete` operator on arrays](https://stackoverflow.com/q/500606/1048572) either, like @charlietfl said! — Bergi, Dec 05 '20 at 17:41

score 2 · Accepted Answer · answered Dec 05 '20 at 17:26

Don't loop through both arrays, instead use an object to map backend ids to values:

const mappings = {};
for (const task of backendtasks) {
    mappings[task.id] = task;
}
for (let i = 0; i < frontendtasks.length; i ++) {
    const curid = frontendtasks[i].id;
    if (curid in mappings) {
        frontendtasks[i] = mappings[curid];
        delete mappings[curid];
    }
}
// push is faster than unshift
for (const key in mappings) {
    frontendtasks.push(mappings[key]);
}

score 2 · Answer 2 · answered Dec 06 '20 at 12:18

Approach: Since you have 2 arrays, I would suggest first normalizing backend array to an object, and then iterate on frontend array and lookup in normalized object as lookup in object is O(1) as compared to O(n) in array.

function getFrontendTasks(){
    const frontendtasks = [
                 {"id": 1, "name": "User Deletion", "script": "UserDeletion"},
                 {"id": 2, "name": "User Creation", "script_name": "UserCreation"}
                ]

    const backendtasks = [
                {"id": 1, "name": "User Deletion", "script": "UserDeletion_V2"}
               ]
               
    const normalizedBackendTasks = backendtasks.reduce((acc, val) => ({...acc, [val.id]: val}), {});

    const newFrontendTasks = frontendtasks.map((task) => normalizedBackendTasks[task.id] || task);

    return newFrontendTasks
    
}

console.log(getFrontendTasks())

score 1 · Answer 3 · answered Dec 05 '20 at 17:52

Creating a mapping table reduces the time complexity from O(n^2) to O(n), by removing the nested for loops, which is very expensive.

Try the following code:

const map = {};
backendtasks.forEach(bt => (map[bt.id] = bt));

frontendtasks.forEach((ft, idx) => {
  if (map[ft.id]) {
    frontendtasks[idx] = map[ft.id];
    delete map[ft.id];
  }
});

frontendtasks = frontendtasks.concat(Object.values(map));

kmp · Answer 4 · 2020-12-06T12:07:28.283

Somehow I didn't see the `map()` function in any solution that creates a new array as shown below.

This will return the new array with the new value. As you can see, it takes an array, an id (this could be anything and any type tho), and a callback.

Searcing for the id in the array and runs the callback when found. Efficient way for what you want to do.

In the callback, I used find() on the backendtasks simply because I need to find the item which has the same id (id: 1).

When found, it returns the item from backendtasks then completes the function by returning that value in the map() function.

So, this should be O(n), considering that the callback only runs once and it's a more elegant solution for multiple uses in my opinion.

const frontendtasks: any[] = [];
const backendtasks: any[] = [];

const fn = (arr: any[], id: number, callback: (removed: any) => any) => {
  return arr.map((ft) => {
    if (ft.id !== id) return ft;
    else return callback(ft);
  });
};

fn(frontendtasks, 1, (rm) => backendtasks.find((id) => rm.id === id));

Efficient way to delete from an array of objects in JavaScript

4 Answers4

Somehow I didn't see the map() function in any solution that creates a new array as shown below.

Somehow I didn't see the `map()` function in any solution that creates a new array as shown below.