admin管理员组

文章数量:1287647

I am working on dictionary application written with react-native.

When I want to filter the array from the search box, I wrote below function. This is working quite good when I test with 2000 word list. But when the word list goes to thousands the search speed is really slow.

So, how can I improve this search function?

//Filter array when input text (Search)

let filteredWords = []
if(this.state.searchField != null)
{
  filteredWords = this.state.glossaries.filter(glossary => {
    return glossary.word.toLowerCase().includes(this.state.searchField.toLowerCase());
  })
}

I am working on dictionary application written with react-native.

When I want to filter the array from the search box, I wrote below function. This is working quite good when I test with 2000 word list. But when the word list goes to thousands the search speed is really slow.

So, how can I improve this search function?

//Filter array when input text (Search)

let filteredWords = []
if(this.state.searchField != null)
{
  filteredWords = this.state.glossaries.filter(glossary => {
    return glossary.word.toLowerCase().includes(this.state.searchField.toLowerCase());
  })
}

• javascript
• arrays
• react-native
• search
• expo

Share Improve this question Follow edited Apr 22, 2018 at 8:13 Zeta 106k1313 gold badges204204 silver badges246246 bronze badges asked Apr 22, 2018 at 8:07 SrasSras 2,29444 gold badges2222 silver badges3333 bronze badges 10

• This kind of questions is suited for CodeReview not StackOverflow. Try posting it there. – ibrahim mahrir Commented Apr 22, 2018 at 8:09
• ... Also Array functions such as filter are quite slow in paraison with regular for loops. If you are trying to make your code faster, then refactor it using a for loop which won't be hard to do. – ibrahim mahrir Commented Apr 22, 2018 at 8:11
• 1 @ibrahimmahrir The question as is lacks a lot of context and would be off-topic in its current form on Code Review. See A guide to Code Review for Stack Overflow users for more information. – Zeta Commented Apr 22, 2018 at 8:11
• 1 @ibrahimmahrir I don't agree. Maybe the question could have been worded better, but this is not about making suggestions on how to improve code quality. This question is about a problem: Bad performance. – Wazner Commented Apr 22, 2018 at 8:12
• It will be hard to answer this question without a description of glossary.word or glossary in general. That being said, binary search instead of includes should yield logarithmic time instead of linear one as long as your dictionary is sorted. – Zeta Commented Apr 22, 2018 at 8:15

 |  Show 5 more ments

2 Answers 2

Sorted by: Reset to default 9

There are multiple factors that are making this code slow:

• You're using filter() with a lambda. This adds a function call overhead for each item being searched.
• You're calling toLowercase() on both strings before calling includes(). This will allocate two new string objects for every parison.
• You're calling includes. For some reason the includes() method is not as well optimized in some browsers as indexOf().

for loop (-11%)

Instead of using the filter() method, I remend creating a new Array and using a for loop to fill it.

const glossaries = this.state.glossaries;
const searchField = this.state.searchField;
const filteredWords = [];   

for (let i = 0; i < glossaries.length; i++) {
  if (glossaries[i].toLowerCase().includes(searchField.toLowerCase())) {
    filteredWords.push(glossaries[i]);
  }
}

toLowerCase allocations (-45%)

Memory allocation is expensive due to the fact that JavaScript uses garbage collection mechanism for freeing used memory. When a garbage collection is performed the whole program is paused while it tries to finds memory which is not used anymore.

You can get rid of the toLowerCase() (inside the search loop) pletely by making a copy of the glossary everytime the glossary is updated, which I assume is not often.

// When you build the glossary
this.state.glossaries = ...;
this.state.searchGlossaries = this.state.glossaries.map(g => g.toLowerCase());

You can also remove the toLowerCase() on the searchText by calling it once before the loop. After these changes, the code will look like:

const glossaries = this.state.glossaries;
const searchGlassaries = this.state.searchGlossaries;
const searchField = this.state.searchField.toLowerCase();
const filteredWords = []; 

for (let i = 0; i < glossaries.length; i++) {
  if (searchGlassaries[i].includes(searchField)) {
    filteredWords.push(glossaries[i]);
  }
}

indexOf() instead of includes() (-13%)

I am not really sure why this is the case, but tests show that indexOf is a lot faster than includes.

const glossaries = this.state.glossaries;
const searchGlassaries = this.state.searchGlossaries;
const searchField = this.state.searchField.toLowerCase();
const filteredWords = []; 

for (let i = 0; i < glossaries.length; i++) {
  if (searchGlassaries[i].indexOf(searchField) !== -1) {
    filteredWords.push(glossaries[i]);
  }
}

Overall the performance has improved by 70%. I got the performance percentages from https://jsperf./so-question-perf

Optimize the algorithm

In the ments you said you would like an example of optimizations that can be done when the requirements are loosened to only match words that start with the search text. One way to do this is a binary search.

Let's take the code from above as starting point. We sort the glossaries before we store it in the state. For sorting case insensitively, JavaScript exposes the Intl.Collator constructor. It provides the pare(x, y) method that returns:

negative value  | X is less than Y
zero            | X is equal to Y
positive value  | X is greater than Y

And the resulting code:

// Static in the file
const collator = new Intl.Collator(undefined, {
  sensitivity: 'base'
});

function binarySearch(glossaries, searchText) {
  let lo = 0;
  let hi = glossaries.length - 1;

  while (lo <= hi) {
    let mid = (lo + hi) / 2 | 0;
    let parison = collator.pare(glossaries[mid].word, searchText);

    if (parison < 0) {
      lo = mid + 1;
    }
    else if (parison > 0) {
      hi = mid - 1;
    }
    else {
      return mid;
    }
  }

  return -1;
}

// When you build the glossary
this.state.glossaries = ...;
this.state.glossaries.sort(function(x, y) {
  return collator.pare(x.word, y.word);
});

// When you search
const glossaries = this.state.glossaries;
const searchField = this.state.searchField.toLowerCase();
const filteredWords = [];

const idx = binarySearch(glossaries, searchField);

if (idx != -1) {
  // Find the index of the first matching word, seeing as the binary search
  // will end up somewhere in the middle
  while (idx >= 0 && collator.pare(glossaries[idx].word, searchField) < 0) {
    idx--;
  }

  // Add each matching word to the filteredWords
  while (idx < glossaries.length && collator.pare(glossaries[idx].word, searchField) == 0) {
    filteredWords.push(glossaries[idx]);
  }
}

As the question doesn't seem to belong on CodeReview, I think there are a few things that you can do to make your code drastically faster [citation needed]:

• Cache that call to this.state.searchField.toLowerCase() as you don't need to call it on every iteration.
• Use regular old for loops instead of flashy-but-slow Array functions.

And here is the final result:

let filteredWords = []
if(this.state.searchField != null) {
    let searchField = this.state.searchField.toLowerCase(),
        theArray = this.state.glossaries;                          // cache this too

    for(let i = 0, l = theArray.length; i < l; ++i) {
        if(theArray[i].word.toLowerCase().includes(searchField)) {
            filteredWords.push(theArray[i]);
        }
    }
}

Edit:

If you want to search for glossaries whose word start with searchField, then use indexOf === 0 instead of includes as the condition like this:

if(theArray[i].word.toLowerCase().indexOf(searchField) === 0) {

本文标签： javascriptHow can I speed up my array search functionStack Overflow