algorithm API design question

[Timon Gehr]

On 09/30/2013 11:59 AM, Peter Alexander wrote:
> On Monday, 30 September 2013 at 09:15:22 UTC, Timon Gehr wrote:
>> On 09/30/2013 04:35 AM, Andrei Alexandrescu wrote:
>>> 2. We should statically specialize find(r1, r2) for the case r2 is an
>>> instance of Repeat. The specialization runs the tailored algorithm. The
>>> user is supposed to call e.g. find(r, repeat(x, k)) to benefit of the
>>> specialized algorithm.
>>>
>>
>> If the specialized algorithm runs faster, this should be done anyway.
>> What is the optimization that would the specialized algorithm run
>> faster though?
>
> This.
>
> The faster algorithm is to presumably jump along for random access
> ranges. e.g. if you are searching for xxxxxxxxxx then check r[9], if
> isn't x, check r[19] and so on. If it is x then check the preceding 10
> elements.

Boyer-Moore will already do this (and more). I guess you can be sure to 
get rid of the helper tables by specialising it manually. (But there is 
no fundamental obstacle that would prevent the compiler to perform this 
partial evaluation automatically).