On Saturday, 28 May 2016 at 12:47:59 UTC, Andrei Alexandrescu
wrote:
On 5/28/16 6:56 AM, qznc wrote:
The sentinel value is `needleBack+1`, but range elements need
not
support addition. Finding a sentinel is hard and most
certainly requires
more assumptions about the ranges.
No need for a sentinel really so long as you first search for
the last element of the needle, in the haystack.
Allow me to put on the table a simple brute force routine,
specialized for arrays with copyable elements, no custom
predicate etc. Far as I can tell it does no redundant work:
A nice one. Here are the numbers I got:
LDC:
std find: 156 ±33
manual find: 117 ±24
qznc find: 114 ±14
Chris find: 135 ±24
Andrei find: 112 ±27
DMD:
std find: 177 ±31
manual find: 140 ±28
qznc find: 102 ±4
Chris find: 165 ±31
Andrei find: 130 ±25
My sentinel idea is to have only one condition branch in the
inner loop. Andrei find still has to `if` in the inner loop. My
inner loop looks like this:
haystack[scout] = cast(typeof(needleBack)) (needleBack+1); //
place sentinel
for (size_t j = scout + 1 - needleLength, k = 0;; ++j, ++k) {
// no condition
if (!binaryFun!pred(haystack[j], needle[k])) { // only
condition
// ... ok in here comes another, but this not as costly
}
}
As long as you are matching the needle, there is only one
condition to check. There is no check for k < needleLength,
because the check always fails for needle[$] aka haystack[scout]
due to the sentinel.
I thought it might be slower, since we need to write to memory
twice instead of only reading. Turns out it is faster.
