On Monday, 23 May 2016 at 22:19:18 UTC, Andrei Alexandrescu wrote:
On 05/23/2016 03:11 PM, qznc wrote:
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?
Andrei
I've played around with some algorithms and kept them as simple
as possible, but I've found that a linear brute force for-loop
always beats them (it's the extra decision(s), I suppose). It
looks nice in theory, but in hardware reality a stupid loop is
more efficient.
NB: I've found that `foreach` is usually faster than a manual
`for`-loop.
I used qznc's benchmarking, and it's clear that the current
implementation of std.algorithm.find is quite a poor performer.
We do have to work on that. Library functions should be fast, no
matter what. If someone uses `find`, they wanna be sure it's
optimized for speed.
