3 ms·
I would have found the article much better if there was more discussion of the "highly efficient indexOf function". It sidesteps the whole discussion of algorit
by archangel_one 15y ago
I would have found the article much better if there was more discussion of the "highly efficient indexOf function". It sidesteps the whole discussion of algorithms to appeal to some magic black box with no explanation of how it works - in this case it seems like the speed advantage might very well be because that's implemented in C rather than his KMP implementation which is all in Python. That's still a valid reason to use the approach instead if it means the result is faster, but I'd have preferred to see some more discussion of what was going on behind the scenes.
- troels 15y agoAgreed. Especially because that would mean that implementing the algorithm at the same level (E.g. in C) would yield much better results than any of the cases.
- tomdeakin 15y agoThis kind of discussion is lacking in the article. It seems as if the OPs goal is optimisation and of course finding the right algorithm with the lowest complexity is the first port of call. However, the indexOf function seems to rely on properties of the data which may not be present (like the forced example in the middle). There are other algorithms besides KMP too for this. I'm sure with some thinking on my part the linear time suffix tree algorithms could solve this too off hand.