How do I make the search in the typeahead widget more efficient

Question

I have a typeahead widget to get the state or city's population according to what the user types

Instead of issuing a GET request every time the user is done typing, the way this typeahead widget works is fetch data beforehand and store it in memory and every time user types, we are iterating through the data to retrieve the stuff that we need.

The live demo is here: https://codesandbox.io/s/saveddatatypeahead-lcyfg?file=/src/index.js

So the data is fetched like this

const data = [];

fetch(endpoint)
  .then(res => res.json())
  .then(result => {
    data.push(...result);
  });

and we listen for the input event on the input field, the timeId is for debouncing the searching, we don't want to search too frequently

searchInput.addEventListener("input", e => {
  if (e.target.value.length > 2) {
    if (timeId) {
      clearTimeout(timeId);
    }
    timeId = setTimeout(() => {
      displayMatches(e.target.value);
    }, 500);
  }
});

and the search is performed here

function findMatches(regex, data) {
  // the time complexity is 
  // O(M x K)
  // M is the length of a city or state
  // K is the keyword to match
  // e.g. M - 'New York' K - 'yo'
  return data.filter(
    place => place.city.match(regex) || place.state.match(regex)
  );
}

Here the regex is constructed based on what the user typed const regex = new RegExp(text, "ig");

So for now it seems to me that the time complexity for the searching here is O(N x M x K) N is the number of entries in the data array, M is the average length of every city or state's name, and K is the keyword the user typed.

So my question is, is there a way to make the search more efficient? For now I have done two things to improve the efficiency.

1.if what the user types is less than 3 characters, we don't perform the search

2.debounce the search and only fire it when the user is done typing

Right the amount of data is not huge but I can see that it doesn't scale well with this naive implementation of search. Maybe building a trie can help? I am not sure.

Also any other suggestions and critiques about this widget are highly welcomed

Answer 1

The way the regular expression engine works is, it iterates along every character in the input string, checking if a match to the pattern starts there. For example, searching for "jose" in "san jose" will result in the match being attempted at index 0, which immediately fails, and the bumpalong increments to index 1, which also immediately fails. This continues until index 4, at which point the j is matched successfully, so the pattern continues, matching o, s, e. When the pattern is just composed of ordinary characters, the length of the pattern doesn't have much of an effect, because on the vast majority of indicies, it'll immediately fail. Rarely, it'll have to iterate a few characters in the pattern before an index fails, eg searching for san jo against San Francisco at index 0, but this is uncommon and still only goes through part of the pattern. So, pattern length doesn't affect computational power required much; it isn't something to worry about.

When turning user input into a regular expression, make sure to escape the input text first, otherwise the constructed pattern's syntax could be invalid or not match what it should. (You could also make a whitelist of characters, and remove any character not on the whitelist from the input)

But for the expensive operation you want to optimize, since it looks like you're just trying to find whether a substring exists in a larger string, a regular expression is overkill - use String.prototype.includes instead. Turn the input and data strings to lower case first, to preserve case-insensitive search - for the data, do this once, on pageload, not inside findMatches. Store the lower-cased results in another property of course, lowerCity and lowerState. There may occasionally have unusual characters like San José, so call String.prototype.normalize on both the input and data, to get a string without accents and diacritics. (You need to use the regex later to construct the HTML, of course, but you don't need to use it when performing the expensive search to find the matching places)

To further cut down on computations required, a possible approach is create an object indexed by characters a to z. Have each property value be an array containing the places that contain that character. Then, when searching for a place, find the least common character in the search string, then look up and search through that array on the object. For example, when searching for "Jose", the least common character is J, so you'd look up the j property. Taking the cities listed on this page as an example, this results in having to search through only 40 cities instead of 2000. (This approach requires a bit more memory, though)

Here's a quick example of the algorithm, taking a few of the places from your gist, and displaying matches as you type:

const places=[{city:"New York",growth_from_2000_to_2013:"4.8%",latitude:40.7127837,longitude:-74.0059413,population:"8405837",rank:"1",state:"New York"},{city:"Los Angeles",growth_from_2000_to_2013:"4.8%",latitude:34.0522342,longitude:-118.2436849,population:"3884307",rank:"2",state:"California"},{city:"Chicago",growth_from_2000_to_2013:"-6.1%",latitude:41.8781136,longitude:-87.6297982,population:"2718782",rank:"3",state:"Illinois"},{city:"Houston",growth_from_2000_to_2013:"11.0%",latitude:29.7604267,longitude:-95.3698028,population:"2195914",rank:"4",state:"Texas"},{city:"Philadelphia",growth_from_2000_to_2013:"2.6%",latitude:39.9525839,longitude:-75.1652215,population:"1553165",rank:"5",state:"Pennsylvania"},{city:"Phoenix",growth_from_2000_to_2013:"14.0%",latitude:33.4483771,longitude:-112.0740373,population:"1513367",rank:"6",state:"Arizona"},{city:"San Antonio",growth_from_2000_to_2013:"21.0%",latitude:29.4241219,longitude:-98.49362819999999,population:"1409019",rank:"7",state:"Texas"}];

const placesByChar = {};
for (const place of places) {
  for (const char of new Set(place.city.toLowerCase() + place.state.toLowerCase())) {
    if (!placesByChar[char]) placesByChar[char] = [];
    placesByChar[char].push(place);
    place.cityLower = place.city.toLowerCase();
    place.stateLower = place.state.toLowerCase();
  }
}
const charFrequencies = [['z',128],['j',188],['q',205],['x',315],['k',1257],['v',2019],['b',2715],['p',3316],['g',3693],['w',3819],['y',3853],['f',4200],['m',4761],['c',4943],['u',5246],['l',7253],['d',7874],['h',10795],['r',10977],['s',11450],['n',12666],['i',13318],['o',14003],['a',14810],['t',16587],['e',21912]]
  .map(([char]) => char);
const input = document.querySelector('input');
const results = document.querySelector('div');
input.addEventListener('input', () => {
  // validate, debounce, and:
  const lowerValue = input.value.toLowerCase();
  const char = charFrequencies.find(([char]) => lowerValue.includes(char));
  if (!char) return;
  results.textContent = '';
  placesByChar[char]
    .filter(place => place.cityLower.includes(lowerValue) || place.stateLower.includes(lowerValue))
    .forEach((place) => {
      results.textContent += place.city + ',';
    });
});

<input>
<div>

Your listener has a bug: if it runs when a displayMatches is currently being debounced, but the input length is 1 or 0, the outer if will not be entered, but the timeout won't be cleared. If you enter text, then clear it, the still-running displayMatches(e.target.value); will display all places. You should clear the timeout regardless - and since you have a reference to the input element already, you can use that instead of e.target.value:

let timeId;
searchInput.addEventListener("input", e => {
  clearTimeout(timeId);
  const { value } = searchInput;
  if (value.length < 3) {
    return;
  }
  timeId = setTimeout(() => {
    displayMatches(value);
  }, 500);
});

Your fetch has no catch. If there are errors (gist deleted, site down, network offline), it would be more user-friendly to display them to the user, rather than having the app silently fail.

You should usually be quite wary of concatenating data into a string that gets inserted as HTML, eg:

<span class='type-ahead__result-city--hl'>${text}</span>

It might be safe with this dataset, but for others, it would allow for arbitrary code execution (and, for example, send the user's login information in their cookies to a malicious actor).

const text = `<img src onerror="alert('evil')">`;
const html = `<span class='type-ahead__result-city--hl'>${text}</span>`;
document.body.innerHTML = html;

Either escape special characters first, or set the text by assigning to the textContent of the element after it's been created.