!in

[Andrei Alexandrescu]

bearophile wrote:
> I've seen this change: http://dsource.org/projects/dmd/changeset/388
> 
> !in is one of the things I have asked in the first list of requests I
> have posted in this newsgroup a lot of time ago :-) Glad to see few
> of those things get implemented. Thank you.
> 
> The related thing I was asking for, is to use "in" for a linear
> search of single items inside an array, as in Python, a very handy
> thing that's used frequently (CPython it also implements an efficient
> algorithm to search for a substring:
> http://effbot.org/zone/stringlib.htm  But probably Andrei wants such
> substring search to be a separated algorithm, even if it's very
> specifically tuned for strings only and not for arrays in general. I
> can understand this).

That algorithm is nice. Generally I'd be hesitant to make it all too 
easy to do linear searches. Too much of that would encourage people to 
stick with linear searches because it's the path of least resistance.

Searching a value in a literal should actually be allowed:

x in [10, 20, 30, 0]

is great because the compiler has complete discretion in how to conduct 
the search (e.g. linear vs. binary vs. hash search; it can take the 
initiative of presorting the literal). But general search in an 
unstructured range... maybe not.

That being said, the CPython string you pointed me to looks very 
interesting. Phobos has a Boyer-Moore search implementation, but, just 
like Fredrik Lundh, I'm unhappy that it does a fair amount of 
computation upfront and that it needs dynamic allocation.

If someone has the time, please contribute a better implementation of 
find() in std.algorithm.


Andrei