Some might argue that this test is unfair to the backtracking implementations, since it focuses on an uncommon corner case. This argument misses the point: given a choice between an implementation with a predictable, consistent, fast running time on all inputs or one that usually runs quickly but can take years of CPU time (or more) on some inputs, the decision should be easy.
Looks as if the answer is really "NFAs (implemented by simulating being in multiple states simultaneously) totally destroy other NFAs (implemented with backtracking)" in speed.
Instead of teaching them in school, it would be better to design a decent UI so that you wouldn't have to "learn" them.
« Older "Chris Supranowitz is a researcher at The Insitute... | Sure, big numbers are fine. Bu... Newer »
This thread has been archived and is closed to new comments
Buy a Shirt