Optimizing search of array of objects

Question

I have an array of objects that is a length of 5,866 like formatted like this {label: "Luke Skywalker", value: "556534"} and I am searching the objects and filtering by their label like so

  onChange = (e) => {
        e.persist()
         this.setState({filter:e.target.value, filtered_array: 
            this.state.raw_user_list.filter(user =>
              user.label.toLowerCase().indexOf(e.target.value.toLowerCase()) > -1)})
    }

...
     <form style={{paddingBottom:'10px'}}>
              Filter: <input name="filter" value={this.state.filter} onChange={this.onChange} type="text" style={{
                border: '1px solid #cccccc',
              }}/>
            </form>

this.state.filter is the value that is being types in to filter. Before I was working with less than 1,000 entries initially and now with the user_list being 5,866 causes performance issues with the way I am filtering. I want to filter the data real-time when the user types.

Don't perform `e.target.value.toLowerCase()` for each iteration. Store it in a scoped variable that you reference from the iteration function. That's one easy fix that should give you immediate results. — Patrick Roberts, Dec 17 '18 at 16:14
Aside from externalizing the lowerCase (you're repeating it each loop), you may think about using some external libraries, if allowed. Fuse.js seems to be your friend in that case specifically: https://github.com/krisk/Fuse — briosheje, Dec 17 '18 at 16:15
Issue is more likely related to how you are using this. 5900 elements is not a lot — charlietfl, Dec 17 '18 at 16:15
Okay let me restructure it based off the comments. I'll look into Fuse.js after. I want to avoid using another library. — Snoopy, Dec 17 '18 at 16:22
Some throttling in the `onChange` would help if it is related to continuous typing — charlietfl, Dec 17 '18 at 16:24
also, if the current filter contains the previous filter, then the current result is a subset of `filtered_array` and you don't have to filter the entire `raw_user_list` again. — Thomas, Dec 17 '18 at 16:47
thinking on these comments of not calling `e.target.value.toLowerCase()` the reason I am doing this is so the filter is real-time. So I think this route wouldn't work — Snoopy, Dec 17 '18 at 16:52
@user10204157 Ok, but you don't have to compute `e.target.value.toLowerCase()` 5866 times (per keypress). — Thomas, Dec 17 '18 at 22:11

Treycos · Accepted Answer · 2019-01-04T09:26:22.530

I can think of 2 ways to optimize your searching function :

Using includes instead of indexOf, wich does not return an index, but only true/false

this.state.raw_user_list.filter(user => user.label.toLowerCase().includes(e.target.value.toLowerCase()))

According to this stack overflow answer, a Regex would be a lot faster (for Chrome in particular) :

this.state.raw_user_list.filter(user => user.label.match(new RegExp(e.target.value, 'i')))

Using the 'i' option in your Regex means that it is case insensitive

UPDATE

According to these tests, your function can be even faster than the previous one with a cached Regex :

const rValue = new RegExp(e.target.value, 'i')
this.state.raw_user_list.filter(user => rValue.test(user.label))

score 1 · Answer 2 · answered Dec 17 '18 at 16:58

You can use a Trie data structure (https://github.com/Draluy/MCsolver/blob/master/src/services/DictService.js)

Basically that will allow you to find words a lot quickier. I used it in a project to store all the words of the dictionnary and searches are tipically under a millisecond.

You can find my implementation here: https://github.com/Draluy/MCsolver/blob/master/src/services/DictService.js

Optimizing search of array of objects

2 Answers2