Javascript fastest way to remove Object from Array

Question

Working on app where speed is crucial, the arrays are huge and the objects contained within the arrays.

I experimented with grep and filter and can not see significant speed difference, varies +- 5ms , also tried looping through array and using .splice(i,1); (same results).

I have a fast machine, if it always take more or less the same time on fast machine, does that mean it will take more or less same time on older machine?

Is there faster way to remove an object from array?

Want to do something like this:

var filterTime = performance.now();
doStuff1();
var filterTimeEnd = performance.now();

var grepTime = performance.now();
doStuff2();
var grepTimeEnd = performance.now();

and then store the differences in cookie, so the next time the page loads or is refreshed, execute most efficient way: removing object from array.

UPDATE

snippet of filter experiment

      companyMasters = companyMasters.filter(function (obj) {
      return obj.masterId != CompanyObj.masterId;
      });

Roughly how many elements are you removing proportional to the array size? — twinlakes, May 18 '15 at 13:41
If you're using grep & filter, there are more permutations here than simply deleting an object from an array. You should take your use case, put into a http://jsperf.com and test on multiple machines — CodingIntrigue, May 18 '15 at 13:42
@twinlakes I am removing one object in array, length is less than 10 000 but it can become much much bigger — Jack, May 18 '15 at 13:54
Are you going to remove only one item from the array, or do you mean that you remove one item at a time? What determines which item(s) should be removed? — Guffa, May 18 '15 at 14:00
@Jack It depends of your app needs and how You use Arrays BUT what if you did not use Array but Object where key is the object ID and value is the object itself. Then removing an object is just ``delete objects.objectId`` which should be fast as lightning. — tiblu, May 18 '15 at 14:03
Fastest way to loop through an array is using a loop: http://stackoverflow.com/questions/5349425/whats-the-fastest-way-to-loop-through-an-array-in-javascript — garryp, May 18 '15 at 14:05
@Guffa removing one item at a time, but will be removing many items. **masterId** determines what will be removed — Jack, May 18 '15 at 14:08
@Jack: How many items will you remove? It can't be so many, as you can't reliably store much information in a cookie. — Guffa, May 18 '15 at 14:13

score 20 · Answer 1 · answered Jan 19 '19 at 18:35

The existing answer already provide good solutions to reducing the runtime complexity of the underlying problem.

However I want to briefly answer the original question as well, since this is the first page when googling for how to remove from an array the most performant way.

Without maintaining order the fastest way to remove by index is removing by assigning the last element to the to be removed index and popping from the array, since this has O(1) runtime complexity.

Array.prototype.mySwapDelete = function arrayMySwapDelete (index) {
    this[index] = this[this.length - 1];
    this.pop();
}

With maintaining order the fastest way to remove by index is shifting in place:

Array.prototype.myShiftDelete = function arrayMyShiftDelete (index) {
    var stop = this.length - 1;
    while (index < stop) {
        this[index] = this[++index];
    }

    this.pop();
}

I have created a JS perf snippet to benchmark the different functions: https://jsperf.com/array-remove-by-index

When wanting to filter, it is also significantly faster to filter in place and shift than calling the native .filter() function, which allocates a new array. This in place filter also maintains order:

Array.prototype.myShiftFilter = function arrayMyShiftFilter (predicate) {
    let i, j;

    for (i = 0, j = 0; i < this.length; ++i) {
        if (predicate(this[i])) {
            this[j] = this[i];
            ++j;
        }
    }

    while (j < this.length) {
        this.pop();
    }
}

See also JS Perf snippet for benchmark: https://jsperf.com/array-filter-in-place

@Kalabasa Doesn't work for arrays with length 1, checking that case gives comparable code complexity while also introducing branching — Maximilian Schier, Oct 10 '19 at 06:44
let list2 = [1, 2, 3]; let itemToRemoveIndex2 = 1; list2[itemToRemoveIndex2] = list2[this.length - 1]; list2.pop(); console.log(list2); gives (2) [1, undefined] — Tom Smykowski, Oct 19 '20 at 18:10
@TomaszSmykowski Yes, indexing list2 with an undefined value returns undefined, you probably want to index with list2.length instead — Maximilian Schier, Oct 20 '20 at 19:58
this is much better.. for those dealing with immutable array, you can use ´Array.from()`. but this still is very fast — Jack, May 22 '22 at 06:13

Mike Brant · Accepted Answer · 2015-05-18T14:10:13.860

19

Any solution in which you need to iterate the array to find a single item would seem to indicate that you have a problem with the data structure you are using. Rather than storing your objects in a numerically indexed array, perhaps your should be storing them in an object where keys are the masterId values that you are going to be trying to do lookups against. At a very minimum, if you need to keep your objects in a numerically index array for some other reason, you could consider building a separate object within which you map the masterId values to the index in the main array where the object resides.

So rather than something like this:

[
    {
        masterId: 'foo',
        ...
    },
    {
        masterId: 'bar',
        ...
    },
    ...
]

You would build your data structure like this:

{
    foo: {
        masterId: 'foo',
        ...
    },
    bar: {
        masterId: 'bar',
        ...
    },
    ...
}

This would allow your code to look like this:

var needle = CompanyObj.masterId;
// delete object set for 'needle' property
delete companyMaster[needle];

This gives you an operation with O(1) time complexity instead of O(n).

edited May 18 '15 at 14:10

answered May 18 '15 at 14:04

Mike Brant

70,514
10
99
103

1

Unfortunately I have to keep the numerically indexed array on the other hand: "building a separate object within which you map the masterId values to the index" is not a bad idea – Jack May 18 '15 at 14:18
@Jack Well unless you can build that map at the same time you are building the array, you will really need to think about whether separate map makes sense. You would have to loop the array to build the map in the first place (an `O(n)` operation). If you are only going to delete one item from the array, you won't really gain much value. But if you have to delete multiple values, you will likely still see benefit. Either way, if you are needing to loop the array for lookup, you should build in a break to bail out of the loop when a match is found, so you don't have to loop the entire array. – Mike Brant May 18 '15 at 14:24
2

If the array is absolutely necessary, I would also have a map object like the one Mike Brant showed. In addition to the ids, those objects could also have an index that shows how you can quickly reach and splice out the masterId in the array. *However*, then you have the problem of needing to update all the map's index references for numbers that came after the deleted one. Ultimately, yeah...this is the reason databases exist, even the JavaScript kind; to store things in a much more accessible way. Your array structure **will cause problems**. Take that info to whoever mandated it. – Katana314 May 18 '15 at 14:34
1

@Jack Actually, in thinking further about the map approach, I don't see that you would get as much benefit out of it as I had thought initially. If you are removing items from the array, that would mean you would need to update the map object after every deletion change mapping to new index values (as these would change with deletions). This would require iteration over the map, so no great benefit would be gained. So even if you have to get the array as input, your best best would be probably to just construct the object mentioned in my answer from the array and then discard the array. – Mike Brant May 18 '15 at 14:56
@MikeBrant yes that is true creating a map will only be waist, constructing the object and discarding the array is a lot less trouble. Katana314 said a database would probably be faster and more stable than expecting the user machine to handle it, perhaps mongoDB – Jack May 18 '15 at 16:09

score 9 · Answer 3 · answered May 18 '15 at 14:16

9

Instead of looping through the array over and over to remove one item at a time, build a map that you can use to filter out all the items at once:

var map = {};
for (var i = 0; i < itemsToRemove.length; i++) {
  map[itemsToRemove[i]] = 1;
}

companyMasters = companyMasters.filter(function (obj) {
  return !(obj.masterId in map);
});

answered May 18 '15 at 14:16

Guffa

687,336
108
737
1,005

1

This is a significant improvement over code in original post as at least you loop the array only once, deleting all items which need to be removed. Looping through separately for each item to be removed will be very problematic. – Mike Brant May 18 '15 at 14:40

Javascript fastest way to remove Object from Array

3 Answers3