faster splitter

[Chris via Digitalmars-d]

On Tuesday, 24 May 2016 at 07:54:38 UTC, qznc wrote:
> On Monday, 23 May 2016 at 22:19:18 UTC, Andrei Alexandrescu 
> wrote:
>> On 05/23/2016 03:11 PM, qznc wrote:
>>> Actually, std find should be faster, since it could use the 
>>> Boyer Moore
>>> algorithm instead of naive string matching.
>>
>> Conventional wisdom has it that find() is brute force and 
>> that's that, but probably it's time to destroy. Selectively 
>> using advanced searching algorithms for the appropriate inputs 
>> is very DbI-ish.
>>
>> There are a few nice precedents of blend algorithms, see e.g. 
>> http://effbot.org/zone/stringlib.htm.
>>
>> Writing a generic subsequence search blend algorithm, one that 
>> chooses the right algorithm based on a combination of static 
>> and dynamic decisions, is quite a fun and challenging project. 
>> Who wanna?
>
> I observed that Boyer-Moore from std is still slower. My guess 
> is due to the relatively short strings in my benchmark and the 
> need to allocate for the tables. Knuth-Morris-Pratt might be 
> worthwhile, because only requires a smaller table, which could 
> be allocated on the stack.
>
> The overall sentiment seems to be that KMP vs BM depends on the 
> input. This means an uninformed find function could only use 
> heuristics. Anyway, Phobos could use a KnuthMorrisPrattFinder 
> implementation next to the BoyerMooreFinder. I filed an issue 
> [0].
>
> Apart from advanced algorithms, find should not be slower than 
> a naive nested-for-loop implementation.
>
> [0] https://issues.dlang.org/show_bug.cgi?id=16066

 From Phobos [1]:

         /* Preprocess #2: init skip[] */
         /* Note: This step could be made a lot faster.
         * A simple implementation is shown here. */
         this.skip = new size_t[needle.length];
         foreach (a; 0 .. needle.length)
         {
             size_t value = 0;
             while (value < needle.length
                    && !needlematch(needle, a, value))
             {
                 ++value;
             }
             this.skip[needle.length - a - 1] = value;
         }

[1] 
https://github.com/dlang/phobos/blob/master/std/algorithm/searching.d#L335