3 ms·

First I thought this was because in drfuchs' version both the array and the key are completely random, so it's not likely the key is found before the end of the

First I thought this was because in drfuchs' version both the array and the key are completely random, so it's not likely the key is found before the end of the array is reached. This is of course the more realistic scenario, whereas my test was only testing the worst case where they key is not part of the array. However, when I modify it to not include they key in the search array (`myarray[i] = random() & 0x7fffffff;`, `key = 0xffffffff;`) I see the same behavior: -O0, i5-2500K naive search average: 1773653.88 ns knuth search average: 1865263.62 ns -O3, i5-2500K naive search average: 590244.25 ns knuth search average: 345119.06 ns

drfuchs 7y ago
Yeah, I was careless on not preserving the nice feature of your code that kept there from ever being a match, figuring that the chances were low of a hit; but of course that assumption went out the window when the array got way bigger. After posting, I noticed the issue, so I made a similar change to yours, and the results didn't change. I do suggest that you change the line that sets 'key' to not make it known at compile-time, to avoid unrealistic optimizations, thus: const int key = random() | 0x80000000; // ensure no match