faster splitter

[Chris via Digitalmars-d]

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:
>
> T[] find(T)(T[] haystack, T[] needle)
> {
>     if (needle.length == 0) return haystack;
>     immutable lastIndex = needle.length - 1;
>     auto last = needle[lastIndex];
>     size_t j = lastIndex;
>     for (; j < haystack.length; ++j)
>     {
>         if (haystack[j] != last) continue;
>         immutable k = j - lastIndex;
>         // last elements match
>         for (size_t i = 0; ; ++i)
>         {
>             if (i == lastIndex) return haystack[k .. $];
>             if (needle[i] != haystack[k + i]) break;
>         }
>     }
>     return haystack[$ .. $];
> }
>
> unittest
> {
>     string s1 = "hello abc world";
>     assert(find(s1, "abc") == "abc world");
>     assert(find(s1, "def") == "");
> }
>
> void main(){}
>
>
> Andrei

I included your function (I also fixed the bug in my 
findStringS_). Here's a typical result:

std find:    208 ±61
manual find: 127 ±29
qznc find:   108 ±13
Chris find:  140 ±32
Andrei find: 126 ±27
=====
std find:    207 ±59
manual find: 128 ±30
qznc find:   108 ±13
Chris find:  141 ±32
Andrei find: 125 ±27

I used dmd, because I don't have ldc on my laptop. qznc's find is 
clearly the winner.