Optimizing an Algorithm to Delete Multiple Keys in JavaScript | by Raphael Yoshiga | Feb, 2022

Finding, isolating and solving an algorithm challenge in a real application

Raphael Yoshiga
Photo by Roman Senkevich on Unsplash
Photo by Andrew Seaman on Unsplash
Profile example

bottleneck

O (keys * prefixes)

O (34000 * 27000) = 917,000,000 iterations

Visual representation of each prefix that must pass through the keys

Back to the problem

Big O (keys + prefixes)

But we can take inspiration from Set’s solution, can we index our data to reduce search cost?

O (keys + prefixes)

O (34000 + 27000) = 61000 instead of

O (34,000 * 27000) = 917,000,000

Compare exponential/linear graph
Credit: Nat Alison

Examples of test cases:

Score in Big O (keys * prefixes) = 12.2 seconds

Implementing a tree indexing approach

Explanation

The end result, before optimization 12.2 seconds, after optimization 65 milliseconds

Leave a Comment