DEV Community

Discussion on: Write a script to identify an anagram

Collapse
 
vinaypai profile image
Vinay Pai • Edited

This algorithm is actually an excellent illustration of why clever algorithms aren't always better.

In fact the clever algorithm here is worse in basically every way imaginable. It's more complicated, limited in scope, error prone, can fail in unexpected ways, and possibly less efficient than the obvious solution.

  • You need to store a lookup table of letters to primes. For the 26 letters, this 26 element lookup table is already more code than it would take to iterate over the characters and increment values in a map.
  • If you typo one of the values you'll get wrong answers all the time. Or you need code to compute the first n primes which comes with its own performance penalty and extra code.
  • The list of primes gets pretty huge if you want to support any kind if i18n and you're dealing with more than just 26 letters.
  • In most languages on modern processors integers are 64 bits long. The 26th prime is 101. In the worst case you could overflow the integers in as few as 10 letters. Integer overflow is DEFINITELY an issue if you're dealing with i18n and therefore more characters and larger primes, or if you want to support phrases rather than individual words, and therefore longer input. Once you overflow and wrap around you could get false positives. Or you could use arbitrary precision arithmetic, but that's drastically less efficient.