What is the highest performance way to filter a list of JSON objects in JavaScript?

Question

Let's assume I have a huge (1000+) list of objects like this:

[{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..]

I want to filter this list by name (character wise).

filter('j') => [{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..]

filter('jo') => [{name: 'john dow', age: 38, gender:'m'}, ..]

filter('dow') => [{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..]

What is the highest performance way to do that? RegEx is obviously one of the keys, ordering the list beforehand if you assume that user usually tend to start names from the beginning may also a good idea, but it only helps in some cases.

Are there any JavaScript built-in functions for mapping a filter? I'd expect those to be faster than JavaScript implementations.

P.S.: Yes I want to filter on client side because of "offline capabilities" I want to offer.

Solution 1

Although a substring index (such as a Suffix tree) would make this faster, the direct search would be:

function (s, l) {
    return l.filter(function (v) {
        return v.name.find(s) !== -1;
    });
}

where s is the query string and l is the list of objects.

Solution 2

From experience, the following algorithm works quite well:

1. When the user types the first letter, you perform a search using Array.filter() perhaps and store that result under whatever the user types (e.g. "j");

2. When the user types another letter (e.g. "o"), you perform the search on whatever was typed before ("j"), reducing the number of items to go through

3. When the user deletes one or more characters you try to find the stored searches based on whatever is left in the search box; if all fails, you show an empty list and invalidate the previously stored searches.

Solution 3

I wouldn't worry too much about performance in this case. A desktop computer should eat up 1000, or 10,000 evaluations without sweat. I would avoid any kind of complex optimisation because the risk of breaking functionality is probably higher than the benefit of slightly efficient processing.

Javascript (ECMAScript 5) does provide new methods for filtering arrays. As a native method it is supposed to be a little faster.

var regex = ...

results = json.filter(function(result) {
   return regex.test(result.name)
}

Array.prototype.filter is supported in modern browsers, see http://kangax.github.com/es5-compat-table/. A patch for older browsers is can be added with this: https://github.com/kriskowal/es5-shim

Solution 4

20000 random items (see filter 20k record with time in realtime)

let dictionary = [];
  var time=0;
  var answer = [];

  var possible = "abcdefghijklmnopqrstuvwxyz";
  function makeid(len) {
    var text = "";


    for (var i = 0; i < len; i++)
      text += possible.charAt(Math.floor(Math.random() * possible.length));

    return text;
  }

  function addWord(number){
    for (var inc=0; inc<number; inc++){
      var wl = 5+Math.floor(Math.random() * 5);
      dictionary.push({word:makeid(wl)});
    }
  }

  function findWord(start){
    return dictionary.filter(function(e){
      return e.word.startsWith(start);
    })
  }


  $(document).ready(function( $ ) {

    addWord(20000);
    $("#time").text( 'Search from ' + dictionary.length + ' random items!' );

    $("#search-input").keyup(function() {
      var term = $(this).val() || '';
      

      if( term ) {

        var init = new Date().getTime();
        var sol = findWord( term );
        time= (new Date()).getTime() - init;
        
        console.log( term );
        $("#answer").text(JSON.stringify(sol));
        $("#time").text( sol.length + ' items found in time ' + time + 'ms' );
      } else {
        $("#answer").text(JSON.stringify(dictionary));
        $("#time").text( 'Search from ' + dictionary.length + ' items' );
      }

    });
  });

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<input id="search-input" placeholder="Search..">
<p id="time"></p>
<p id="answer"></p>

https://jsfiddle.net/maheshwaghmare/cfx3p40v/3/

Solution 5

From simple to more complex (no additional libs):

1. Limit search for minimum x chars (usually 3 is acceptable)
2. Delay the filtering while the user is typing using timeout:

//clear previous timed filtering
if (typingTimeout) {
      clearTimeout(typingTimeout);
      typingTimeout = null;
    }
//schedule new filtering
typingTimeout = setTimeout(() => {
   // do some filtering
}, 2000); //acceptable 1-2s

3. If you still wish for faster filtering, You can group your list alphabetically in an object:

{
   A: ['Aron', 'Arnold', ...],
   B: ['Baby'],
   ....
}

Then filter them using the prefixed lists with the first char entered. It is just an example, you should group your data as you see fit (maybe first 2 letters...).

Here is a function that I implemented to help prefix my array:

export function prefixStringsArray(arr, prefixLength) {
  const prefixArr = arr.map((s) => s.substr(0, prefixLength));
  const filter = (item, query) =>
    item.toLowerCase().startsWith(query.toLowerCase());

  const prefixObj = {};
  for (const pre of prefixArr) {
    prefixObj[pre] = arr.filter((item) => filter(item, pre));
  }

  return prefixObj;
}

You should know that using JS object is a very good bet because they are accessed in O(1) (it is sort of a hash map) and if you group your data optimally you'll get small arrays to filter.

Notes:

1. If you choose to prefix your array you should watch out for the user searching query.length < prefixLength
2. This gave me great results in mobile development (React native)
3. The code is only a draft - manually tested

View more solutions