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

Discovering, isolating, and fixing an algorithm problem in an actual software

Raphael Yoshiga
Picture by Roman Synkevych on Unsplash
Picture by Andrew Seaman on Unsplash
Instance profiler

The bottleneck

O(keys * prefixes)

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

Visible illustration of every prefix having to loop by the keys

Again to the issue

Massive O(keys + prefixes)

However we will take inspiration on the Set answer, can we index our information to cut back the lookup value?

O(keys + prefixes)

O(34000 + 27000) = 61,000 as a substitute of

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

Exponential / linear chart comparability
Credit score: Nat Alison

Instance take a look at instances:

End result with Massive O(keys * Prefixes) = 12.2s

Implementing the tree indexing strategy


The ultimate end result, earlier than optimisation 12.2s, after the optimisation 65ms

More Posts