How can I loop through a large UL list faster?

Question

I have a dropdown in a project that I'm building in Google Sheets that has a search function but it takes 15 seconds or more to update the list. How can I make a search function for a large list (in this instance, 16k items) that updates quickly?

Here's what I've got.

The HTML

<div id="cityList">
  <div>
    <input type="text" id="citySearch" oninput="filterCities">
  </div>
  <ul>
    <li> {list of items generated from function} </li>
  </ul>
</div>

The Javascript

function filterCities() {
    var cities = document.querySelectorAll('#cityList ul li')
    var query = document.querySelector('#citySearch').value

    for (i = 0; i < cities.length; i++) {
        if (cities[i].innerText.includes(query) == false) {
            cities[i].classList.add('hide')
        } else {
            cities[i].classList.remove('hide')
        }
    }
}

The CSS

.hide {
     display: none;
}

The unordered list is generated from a function when the HTML loads. For this project, users will need to set a location and the list of cities comes from the API that requires the setting.

What I've Tried

Through some testing, I've learned that both the includes() and the classList.add are the primary issue here. When I test my functions in the browser console on an object, rather than an HTML list item it's acceptably quick (not fast, but not user-experience breaking). Some things I've tried to remedy this are:

• Changing classList.add to classList.toggle. This didn't notably improve the speed.
• Changing classList.add to className += ' hide'. This also didn't notably improve the speed

What I plan to try next is to filter the list as an object and essentially 'replace' the list oninput. I suspect this might be faster but still take a few seconds to write the li elements to the page.

Is there a way to search through a large list of items and filter them that is acceptably responsive on the front end?

Answer 1

Move your source of truth of data out of the DOM, and into vanilla Javascript data (objects and arrays). Don't touch every DOM element on every search, instead, build an entirely new list every time with the matched elements.

You should probably also debounce your search, and limit the number of matches.

Regardless, this is pretty much instant on 16k entries. See these strategies applied in this CodePen.

Abbreviated code, but there's nothing special here, it's basically just filtering an array:

const MIN_SEARCH_LENGTH = 0;
const DEBOUNCE_MS = 200;

const resultContainer = document.getElementById('result');
const resultCountContainer = document.getElementById('resultCount');

const debounce = (func, delay) => {
  let debounceTimer;
  return function() {
    const context = this;
    const args = arguments;
    clearTimeout(debounceTimer);
    debounceTimer = setTimeout(() => func.apply(context, args), delay);
  }
}

const search = (searchText) => {
  const lowered = searchText.toLowerCase();
  const found = new Set();
  if(searchText.length > MIN_SEARCH_LENGTH) {
    const matched = window.lowerCased.reduce((indices, lower, index) => {
      if(lower.includes(lowered)) {
        found.add(window.cities[index]);
      }
      return indices;
    }, found);
  }
  return [...found];
}

const applyFilter = (searchText) => {
  const foundCities = search(searchText);
  const total = foundCities.length;
  resultContainer.innerHTML = foundCities.map(c => `<li>${c}</li>`).join('');
  resultCountContainer.innerText = `Found ${total} result${total > 1 ? 's' : ''}`;
}
const onChange = (e) => applyFilter(e.target.value);
const debounced = debounce(onChange, DEBOUNCE_MS);

const input = document.getElementsByTagName('input')[0];
input.addEventListener('keyup', debounced);

window.cities = ["New York"...];
window.lowerCased = window.cities.map(c => c.toLowerCase());