Filter Array with Multiple object and multiple filter

Question

I have this array that needs to be filtered, it consists of many objects, was using a loop, it's effective but really slows my apps down I'll simplify my array.

let arrayToFilter = [{id:1,month:'Dec'},{id:2,month:'Nov'},{id:3,month:'Feb'},{id:4,month:'Nov'},{id:5,month:'Jan'}]
let filter = ['Dec','Nov']

without looping (for var i =0 ..... ) how to only show data of array with month Dec & Nov? or using a filter. from JavaScript? I need it to be fast (not slowing down my apps), efficient, and effective.

Thanks before

Answer 1

I would use a Set for the filter due to its O(1) time complexity

For example

// Generate random sample data
const length = 6000
const months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]

const arrayToFilter = Array.from({ length }, (_, i) => ({
  id: i + 1,
  month: months[Math.floor(Math.random() * months.length)]
}))

const filter = ['Dec','Nov'] // whatever you've actually got

const hashset = new Set(filter)

const t1 = performance.now()

// Filter the array
const filtered = arrayToFilter.filter(({ month }) => hashset.has(month))

const t2 = performance.now()

console.log(`Operation took ${t2 - t1}ms`)
console.info(`${filtered.length} results`, filtered)

.as-console-wrapper { max-height: 100% !important; }

Answer 2

If you have well defined criteria, you could try something like precomputing an index over the keys you are filtering over. Initially it will take the same time as doing a single filter operation but after will be instant.

const MONTHS = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"];

const bench = (tag, fn) => {
  const now = performance.now();
  fn();
  console.log(`${tag} executed in ${performance.now() - now}ms`);
};

// this is just to create a ton of elements.
const data = Array.from({ length: 1000000 }, (_, i) => {
  return { id: i, month: MONTHS[Math.random() * 12 | 0]};
});

const index = new Map();

for (datum of data) {
  const bucket = index.get(datum.month);
  
  if (bucket == null) {
    index.set(datum.month, [datum]);
  } else {
    bucket.push(datum);
  }
}

bench('filter [Dec, Nov]', () => {
  ['Dec', 'Nov'].reduce((r, f) => r.concat(index.get(f)), []);
});


bench('filter [Nov, Feb, May]', () => {
  ['Nov', 'Feb', 'May'].reduce((r, f) => r.concat(index.get(f)), []);
});


bench('filter [Apr, Dec, Feb, Jan, Jul]', () => {
  ['Apr', 'Dec', 'Feb', 'Jan', 'Jul'].reduce((r, f) => r.concat(index.get(f)), []);
});

On my PC/Browser im filtering 1M records in roughly 0.3ms - 2ms depending on the complexity of the filters. That's within a frame(60fps).

If you want, you could create a function that generates an index for you that you can use to filter on.

const createIndexOn = (date, selector) => {
  const index = new Map();

  for (datum of data) {
    const bucket = index.get(datum.month);
  
    if (bucket == null) {
      index.set(datum.month, [datum]);
    } else {
      bucket.push(datum);
    } 
  }

  return index;
};

const monthIndex = createIndexOn(data, (d) => d.month);

If you need to do something like compound filters where you have say a month and a name, you could create an index on month, filter the results by month, create a index based on the results over name and filter by name. You could also create 2 discrete indexes and just take an intersection. Either way its pretty fast.

This all is predicated that you profiled the code and know that looping over 6000*|Filters| is slow(its probably fine honestly until you hit say 100k). The problem could be else where. For example if you are using react and you are filtering every time a component changes, you should memo the results or use other performance tuning tools.