Suggestion: Operator `in` for slices
ajieskola at gmail.com
Sun Dec 19 10:10:21 UTC 2021
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.
More information about the Digitalmars-d