On Tuesday, 28 October 2014 at 14:06:27 UTC, Steven Schveighoffer wrote:
> On 10/28/14 9:50 AM, "Nordlöw" wrote:
>> Has there been any proposals/plans to make operator "in" work for
>> elements in ranges such as
>>
>>     assert('x' in ['x']);

…

> Your assertion requires O(n) performance.

It is O(ln(n)) on a sorted array.

On 10/28/14 3:45 PM, "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= <ola.fosheim.grostad+dlang@gmail.com>" wrote:
> On Tuesday, 28 October 2014 at 14:06:27 UTC, Steven Schveighoffer wrote:
>> On 10/28/14 9:50 AM, "Nordlöw" wrote:
>>> Has there been any proposals/plans to make operator "in" work for
>>> elements in ranges such as
>>>
>>>     assert('x' in ['x']);
>
> …
>
>> Your assertion requires O(n) performance.
>
> It is O(ln(n)) on a sorted array.

It's also O(lgn) on a sorted set, or O(1) on a hash set. So?

-Steve

On Tuesday, October 28, 2014 18:38:18 via Digitalmars-d-learn wrote:
> To answer your question: Computational (or memory) complexity is not an implementation detail, because it has a very noticeable effect. Therefore, one should not hide an O(n) or worse operation behind a harmless looking expression. It's not a technical requirement, of course, but a convention that makes a lot of sense IMO.
>
> D is relatively consistent in this respect. Not only does it apply to `in` and the aforementioned indexing and slicing, but there's also the convention that ranges shouldn't provide operations they cannot implement cheaply. For example, a singly-linked list shouldn't provide `back` and `popBack()` primitives, because while it is possible to implement them, they would be expensive, which could surprise an unsuspecting user.

Indeed. And the other thing that needs to be taken into account is generic code. A function templated on type T which uses in on that type can rely on in being O(lg n) at the worst, whereas if in worked with something like arrays, then it would suddenly be O(n), which could have a huge impact on performance depending on where the function was used. This is why both C++ and D provide the computational complexity of the operations on their standard container types and in some cases require that a particular operation have no worse than a particular complexity. Without that, algorithms can't make guarantees about their complexity, and it could have very negative impact on the performance of some programs.

- Jonathan M Davis

On Tuesday, 28 October 2014 at 19:24:00 UTC, Steven Schveighoffer wrote:
> https://github.com/schveiguy/dcollections/blob/master/dcollections/HashSet.d
>
> -Steve

Thanks!

> Without that, algorithms can't make
> guarantees about their complexity, and it could have very negative impact on
> the performance of some programs.
>

Yeah. For the programs where efficiency matters but that are
never ever profiled.

On Tuesday, 28 October 2014 at 20:24:03 UTC, Steven Schveighoffer wrote:
>
> It's also O(lgn) on a sorted set, or O(1) on a hash set. So?

As araq points out this should be caught in profiling.

Avoiding generality is not the best approach. A linear scan of a SIMD friendly array that is in cache may be a lot faster than your hash set.