algorithm API design question

[Andrei Alexandrescu]

On 9/30/13 5:04 AM, Timon Gehr wrote:
> 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).

B-M has significant preprocessing costs, so it's not appropriate for all 
cases. A function specialized in finding runs would be optimal without 
preprocessing. Another way of looking at it: it's wasteful to pass 
repeat(x, k) into Boyer-Moore to have it rediscover what the caller knew 
already statically.


Andrei