1

In "Rob Pike's 5 Rules of Programming", he states, "Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. " and as the next rule he states that "Fancy algorithms are buggier than simple ones, and they're much harder to implement." What does he means by "fancy" algorithms? What are some fancy algorithms and what makes them fancy?

1
  • 2
    It's simply the opposite of simple, it doesn't have a formal meaning. May 12 '16 at 14:19
8

"Fancy" in this case is the opposite from "Simple".

Take route finding, for example. A "simple" algorithm would be Dijkstra's algorithm. A "fancy" algorithm would be, for example, bidirectional Simplified Memory-Bounded A*.

The "simple" algorithm doesn't look very good when you look at it's big-O runtime complexity, but you can write it quickly and it gets you the result you want.

The fancier algorithm might lead to better results in most cases, but at the cost of requiring much more code to do so which means much more possibility for bugs to hide. Also, the more complex the algorithm, the more likely that it has some exotic corner-cases where it behaves much worse than expected. So while it might save processor time, it might be far costlier regarding development time, because all that additional code requires more time to develop and even more time to maintain.

As a rule of thumb you should implement a "simple" algorithm first, and only when it turns out that it is not fast enough, look for a more "fancier" implementation.

Edit: Another example where the "size of n" argument applies more would be pseudorandom number generators. A "simple" linear feedback shift register has an internal state equal to the output size, while the far fancier Mersenne Twister has an internal state of 2.5Kb. When you only need a short series of random numbers, the cost of initializing the internal state of the MT will far outweigh the advantages it has.

When you compare two algorithms where one has a runtime of c * log(n) and the other a runtime of c * n², keep in mind that you are looking at different values of c. Given a very large dataset, the first algorithm will break even eventually, even when its c is several orders of magnitude larger. But for smaller values of n a smaller value of c might be more important.

1
  • 2
    There's also the "Clojure motto" log_32 is pretty constant, which refers to the fact that even though Clojure's arrays are actually implemented as trees and not contiguous memory locations and thus have O(log n) amortized access instead of O(1), the branch width is 32, which means that even an array with 4 billion elements (which is the maximum a native Java array, the natural performance comparison for Clojure, can handle), the tree is only about 6.4 levels deep, so you will have a maximum of 7 indirections compared to a native array, which is still plenty fast. May 12 '16 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.