Suggestion: Operator `in` for slices

[Dukc]

On Saturday, 18 December 2021 at 20:46:06 UTC, Dennis wrote:
> On Saturday, 18 December 2021 at 18:47:33 UTC, Adam Ruppe wrote:
>> The `in` operator on AAs has a speed of O(log n) or O(1). `in` 
>> on slices would exceed that being O(n).
>
> Who do people keep repeating that?
>
> - Worst case time complexity of the `in` operator in AA's is 
> actually O(n). This can easily happen in practice when your 
> `toHash` has a poor implementation, which I have had before
>
> - In custom types you can overload the `in` operator to 
> something with arbitrarily bad time complexity.

These are bugs. The O(log n) assumption still makes sense when 
your code works as it's supposed to.

>
> - Despite scaling with O(n), a linear scan is pretty fast. You 
> can probably scan your entire RAM in a matter of seconds.

A few seconds is by far too much. Remember, the data structure 
might be fed to function designed by introspection. The function 
sees "Ah, an `in` operator. `in` is on average O(log N) at worst, 
I can call it hundreds of times without significant slowdown", 
and compiles such that it takes a quarter of an hour to execute.

Had the `in` operator respected the O(log N) assumption, the 
introspecting function would have failed to compile alerting the 
programmer, or used an alternative, quicker implementation.