Filtering a large javascript object recursively

Question

I am filtering a large javascript object (JSON file of 37000 lines) recursively in react. After i have filtered the object i send it down as props to a component that renders the object.

This is my current function and its working fine for all of the smaller files, but its pretty slow for the larger one's. Are there any improvements i could make to the function to make it perform faster?

export const filterBySubstringKey = (data: any, value: string) => { const iterate = (object: any, result: any) => { return Object.keys(object).reduce((acc, key) => { let tempResult = {}; if (key.toLowerCase().indexOf(value.toLowerCase()) !== -1) { result[key] = object[key]; return true; } if (object[key] !== null && typeof object[key] === 'object' && iterate(object[key], tempResult)) { result[key] = tempResult; return true; } return acc; }, false); }; let result = {}; iterate(data, result); return result; };

First optimisation I can see value.toLowerCase(), just do this once and store in a var. — Keith
– Keith, Commented Jun 7, 2020 at 15:32
Next -> Object.keys, since you are potentially after the value too, you could maybe change to Object.entries instead of object[key] — Keith
– Keith, Commented Jun 7, 2020 at 15:35
Thanks for the suggestions. Changing the lowerCase value is a quick one. I have however a separate similar function being called when i am searching by value. — user13700773
– user13700773, Commented Jun 7, 2020 at 15:43
You could try to rewrite your code to use a loop instead of recursion, as a loop is generally faster (stackoverflow.com/questions/9386375/…) — Nils Schlüter
– Nils Schlüter, Commented Jun 7, 2020 at 16:17

trincot · Accepted Answer · 2020-06-07 18:50:16Z

There is not much you can do, but I would suggest the following, which may slightly improve the timings:

Don't pass the second argument to iterate, but make it that the return value is the object you want to get from it.
Use oldfashioned for loops instead of array methods.
Like in comments you already said you did: call value.toLowerCase() only once.
Read from object[key] only once
Use includes instead of indexOf

export const filterBySubstringKey = (data: any, value: string) => { value = value.toLowerCase(); const iterate = (object: any) => { let result = {}; for (let key in object) { // Assuming no enumerable inherited props let val = object[key]; if (key.toLowerCase().includes(value)) { result[key] = val; } else if (val !== null && typeof val === 'object') { let temp = iterate(val); if (temp) result[key] = temp; } } for (let key in result) return result; // When result is not empty // default: return undefined }; return iterate(data); };

Dmytro Biletskyi · Accepted Answer · 2020-06-07 20:54:46Z

I created 3 variants. I slightly simplified your code. Here are performance results jsperf. Results differ from run to run, but variant 4 is the fastest

Edit: Added some more optimization in v5, it outperforms all other.

const filterBySubstringKey5 = (data, value) => { const valueLow = value.toLowerCase() const iterate = object => { let res = {}; for (const key in object) { const ok = object[key] if (typeof ok === "object") { res[key] = iterate(ok); } else { if (key.toLowerCase().indexOf(valueLow) !== -1) { res[key] = ok; } } } return res; }; return iterate(data); };

const filterBySubstringKey2 = (data, value) => { const iterate = object => { return Object.entries(object).reduce((acc, [key, val]) => { if (typeof val === "object") { acc[key] = iterate(val); } else { if (key.toLowerCase().indexOf(value.toLowerCase()) !== -1) { acc[key] = val; } } return acc; }, {}); }; return iterate(data); }; const filterBySubstringKey3 = (data, value) => { const iterate = object => { return Object.keys(object).reduce((acc, key) => { if (typeof object[key] === "object") { acc[key] = iterate(object[key]); } else { if (key.toLowerCase().indexOf(value.toLowerCase()) !== -1) { acc[key] = object[key]; } } return acc; }, {}); }; return iterate(data); }; const filterBySubstringKey4 = (data, value) => { const iterate = object => { let res = {}; for (const key in object) { if (typeof object[key] === "object") { res[key] = iterate(object[key]); } else { if (key.toLowerCase().indexOf(value.toLowerCase()) !== -1) { res[key] = object[key]; } } } return res; }; return iterate(data); };

Your versions will output a different result than the OP's code. (1) if a property value is null, your code will break; (2) if a key matches the given value, but the property vale is an object (or null), you will still call the iterate recursively, (3) Your iterate can return an empty object. This is not simplification, but change in behaviour. And so a timing comparison with the original is not really meaningful.

Collectives™ on Stack Overflow

Filtering a large javascript object recursively

2 Answers 2

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Linked

Related