On: Knuth-Morris-Pratt string-searching algorithm: DFA-less version

[klodolph]

    search_ok("ooooooooooooooo", 15)

30 memory accesses. length times two. The article is correct.

[mlyle → klodolph]

> 30 memory accesses. length times two. The article is correct.

vs. what I said:

> > No, there's one memory access on *average*

[klodolph → mlyle]

Ah, you must have missed the part where the article says “at worst”.

Even if it didn’t say that, I think we can figure out from context that the article is talking about worst-case memory accesses.

[kyberias → klodolph]

No, it clearly says two memory accesses per character.

"At worst" calculation is just calculating the worst case (string not found) where it has to scan the whole string and... access each byte twice.

It doesn't matter whether we have a worst case or not. They claim two memory accesses per character.

[klodolph → kyberias]

> It doesn't matter whether we have a worst case or not. They claim two memory accesses per character.

Yes, a worst case of two memory accesses per character. This is obvious, no?

When people analyze algorithm runtime it is not always explicitly stated whether the author is doing worst-case or average-case analysis. So, as a reader, you sometimes have to figure it out.

[mlyle → klodolph]

It says at worst later, talking about if there is no match. It heavily implies that there's 2 accesses per byte always.

[klodolph → mlyle]

> It says at worst later, talking about if there is no match.

The article says “len*2 at worst”. There is no intervening text, that’s a direct quote.

> It heavily implies that there's 2 accesses per byte always.

This interpretation is incorrect. The article does not imply this.

[mlyle → klodolph]

"You see, there are two memory accesses per one character of the input string."

It says this, DIRECTLY, not qualifying it as "up to" or "worst case". The next sentence says it can be 2*len, e.g. if you scan the entire length.

Those two sentences feel like something that someone would write if they didn't understand short circuit evaluation.

You read it differently, but your opinion of how it is intended isn't sufficient to refute my interpretation of the text.

[klodolph → mlyle]

It seems much more plausible to me that the author does understand short-circuit evaluation, but did not feel like explaining it in such detail to satisfy the tedious pedantry of HN comments.

My experience with writing answers Stack Overflow is that people in the comments will always figure out a way to interpret an answer as being incorrect, and latch onto it.

There is a tradeoff between clarity and pedantry. You don’t want to simplify something too much where it is no longer insightful, and you don’t want to write something with irrelevant detail that obscures the point you are trying to make.

[mlyle → klodolph]

I really don't think the author is fluent in C. They consistently put semicolons after brackets, and they have off-by-1 errors in array indexing, etc (the first search_ok looks past the end of string; the second search_ok won't see ok in the string "ok"). That's part of why I read it that way.

I understand the concern over excessive pedantry.

[klodolph → mlyle]

My experience is that C programmers with many years of experience will still make off-by-one errors. Most of the examples have the correct bounds. The semicolons don’t belong but… so what?

If you wish to report errors to the author, there is an email address at the bottom:

> Please drop me email about bug(s) and/or suggestion(s):