0

I need a faster way to get all the same elements from an array existing in another one.

I have two really large arrays (A and B) with Date objects (>100k elements). Array B contains a subset from elements in Array A. I need Array A filtered for elements that are contained in Array B. So, why not just use Array B directly? I need to preserve the reference from Array A.

Currently I'm using this code:

const A = [];
const B = [];

const result = A.filter((s) => {
     return B.indexOf(s) !== -1;
});

This way is quite slow. It needs over 2min to perform that action with my arrays.

CertainPerformance
  • 356,069
  • 52
  • 309
  • 320
Werewolve
  • 2,448
  • 5
  • 24
  • 38
  • are they arrays of just Date objects, or arrays of objects that contain Date objects? It would help to see an example of an element in each array. – Always Learning Feb 08 '20 at 20:32

2 Answers2

6

Turn the B array into a Set first. Set#has is O(1), but Array#indexOf / Array#includes is O(n):

const bSet = new Set(B);
const result = A.filter(item => bSet.has(item));

That'll improve performance a ton. You might be able to make it a tiny bit faster by using a for loop instead of filter, but the improvement will probably be pretty small.

This works when both arrays contain primitives or contain references to the same objects. If the objects are different, neither .indexOf nor .has nor .includes will work, in which case the strategy would be to somehow serialize all of the objects in B to a Set of primitives first, then carry out the same operation when iterating over A to see whether it's included in B.

Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
CertainPerformance
  • 356,069
  • 52
  • 309
  • 320
0

If you have flexibility with the types, you can always have B contain a pointer to a parent A, this you don't need to search through all of the sub elements of an A to deterrmine if you will find B there - but I am not certain if a B can have multiple A etc etc...

Watachiaieto
  • 417
  • 3
  • 10