Hacker News Reader

As I understand this, the KMP function uses an optimal algorithm, while the indexOf version uses a suboptimal algorithm but takes advantage of a native (C) implementation found in the standard library.

It follows that the fastest approach should be to implement the KMP algorithm natively, using Pyrex rather than C should make this fairly trivial.

View on HN

>It follows that the fastest approach should be to implement the KMP algorithm natively

Not exactly - well, depends what you mean by "fastest". The KMP algorithm is optimal in the worst case, not necessarily in the average case. If you implemented KMP in C and then fed it typical rather than pathological strings, you might still do better with the indexOf algorithm.

besides Pyrex, there's also Cython (I don't know if one superseeded the other or what exactly their relationship is)

Pyrex is the original. Cython is the fork by people who wanted to add more features.

I think their relationship is reasonable, but not reasonable enough for the two projects to link to each-other.

Reply on news.ycombinator.com