2 ms·
Golang single core version: if (b[n]) == (find[found]) { Isn't indexing an UTF-8 string "find" O(n)? To get 10000th char, you need to iterate all 9999 pre
by vardump 9y ago
Golang single core version:
if (b[n]) == (find[found]) {
Isn't indexing an UTF-8 string "find" O(n)? To get 10000th char, you need to iterate all 9999 previous characters first.
Edit: Clarified I'm talking about string "find" and not byte array "b".
- pbourke 9y agoI don't know Go, but b and found appear to be byte arrays, not strings, which would imply O(1) indexing.
- vardump 9y agoSingle core version: find := "07123E1F482356C415F684407A3B8723E10B2CBBC0B8FCD6282C49D37C9C1ABC" That's definitely a string. Otherwise (single core) golang code seems to be just a test whether the compiler is smart enough to remove branch in this code: if (b[n]) == (find[found]) { found += 1 } else { found = 0 } I wouldn't be too surprised if golang compiler generates superfluous range checks costing even more performance. At least golang 1.4 seemed to generate a lot of unnecessary checks in code I optimized a few years ago. Hopefully newer versions are better.
- pbourke 9y agoyep, my mistake - was looking at multicore
- mappu 9y agoNo, that's not how it works - indexing a string returns a byte, and strings have len() their bytes in UTF8. Ranging a string does return unicode runes, however, but ranging is obviously O(n) anyway. https://play.golang.org/p/oyaChPTb576 https://play.golang.org/p/oyaChPTb576