Back

adamham.dev

Optimising a search filter algorithm (Firefox DevTools Console)

June 26, 2020

My latest contribution to Firefox DevTool is the search history in the Console. I've been working with Nicolas Chevobbe to deliver this feature.

The requirements for displaying the search history:

  • Show a maximum of 5 items (There can be upto 100 items in search history)
  • Show the most recent items
  • List the items in alphabetical order
  • Persist between browser sessions

Originally I thought to filter out the matching items, then take the first 5 results and sort them.

The code looks very succinct and it reads very easily.

const LIMIT = 5; const searchHistory = [ /** ... items */ ]; function filter(filterText) { return searchHistory .filter((item) => item.includes(filterText)) .slice(0, LIMIT) .sort(); }

Let's talk about the time complexity of this algorithm:

N = searchHistory.length

So first we will run the filter (a linear operation) N times. M = filtered searchHistory length. In the worst case M can be N so lets just use that for now.

Then we slice which is a constant operation O(1).

Since we have limited the size of the Array to 5 before sorting, the sort can also be treated as a constant operation of O(1).

This leaves us with a time complexity of:

O(N)

Optimising

We know that no matter what in the worst case scenario we will have O(N) assuming we have to reach the end of the input array to satisify the conditions.

However we can definitely improve our best case scenario. By adding the filtered items to a new array we know that we can break out of the loop if we reach our limit of 5 results.

const LIMIT = 5; const searchHistory = [ /** ... items */ ]; function filter(filterText) { const results = []; for (let i = 0; i < searchHistory.length && results.length < LIMIT; i++) { const current = searchHistory[i].toLowerCase(); if (current.includes(filterText) && current !== filterText) { results.push(searchHistory[i]); } } return results.sort(); }

Benchmarking

As you can see from the results of our test case, the optimised version runs 2x as fast as the unoptimised version, although theoretically they have the same time complexity.

View the results at jsbench

Benchmark