www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - More uses of operator "in"

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Has there been any proposals/plans to make operator "in" work for 
elements in ranges such as

     assert('x' in ['x']);

I'm missing that Python feature when I work in D.
Oct 28 2014
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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']);

 I'm missing that Python feature when I work in D.


No. The implication of 'in' for AAs is that it is a fast, O(lgn) or 
better, operation. Your assertion requires O(n) performance.

-Steve
Oct 28 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 28 October 2014 at 14:06:27 UTC, Steven Schveighoffer 
wrote:

 No. The implication of 'in' for AAs is that it is a fast, 
 O(lgn) or better, operation. Your assertion requires O(n) 
 performance.


What about making it work for (builtin) tuples? Then it could be 
make use of a variadic std.algorithm: find() or some lazily 
defined hash-table.

Maybe it could be part (if not already there) of Kenjis great 
tuple improvement PR which is awaiting review and merge.
Oct 28 2014
prev sibling parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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.
Oct 28 2014
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Oct 28 2014
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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.
Oct 29 2014
prev sibling parent reply "Baz" <basile.burg gmx.com> writes:
On Tuesday, 28 October 2014 at 13:50:24 UTC, Nordlöw wrote:

 Has there been any proposals/plans to make operator "in" work 
 for elements in ranges such as

     assert('x' in ['x']);

 I'm missing that Python feature when I work in D.


There is also something similar in Pascal, at the language level. 
Very handy when working with characters or enums.

I think in D it's possible to create some library types which 
allow an almost similar syntax. For example this one, briefly 
written after reading your post:

----
import std.stdio;

// global variable to get rid of 
https://issues.dlang.org/show_bug.cgi?id=11877
CharSet charSet;
struct CharSet
{
     private string str;
     public:
         typeof(this) opSlice(char lo, char hi)
         {
             CharSet result;
             foreach(c; lo .. hi)
                 result.str ~= c;
             return result;
         }
         typeof(this) opSlice(char lohi)
         {
             CharSet result;
             result.str ~= lohi;
             return result;
         }
         bool opIn_r(char elem)
         {
             if (str == "")
                 return false;
             else
                 return ((elem >= str[0]) & (elem <= str[$-1]));
         }
         string toString()
         {
             return str;
         }
}

void main(string args[])
{
     auto a2k = charSet['a' .. 'k'+1];
     auto A2K = charSet['A' .. 'K'+1];
     auto Z29 = charSet['0' .. '9'+1];

     assert( 'a' in a2k );
     assert( !('x' in a2k) );

     assert( 'A' in A2K );
     assert( !('X' in A2K) );

     import std.conv;
     assert( to!string(Z29) == "0123456789" );

     assert( 'x' in charSet['x'..'x'+1] );
}
----
Oct 28 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Tuesday, 28 October 2014 at 15:11:01 UTC, Baz wrote:

 On Tuesday, 28 October 2014 at 13:50:24 UTC, Nordlöw wrote:

 Has there been any proposals/plans to make operator "in" work 
 for elements in ranges such as

    assert('x' in ['x']);

 I'm missing that Python feature when I work in D.


 There is also something similar in Pascal, at the language 
 level. Very handy when working with characters or enums.


AFAIR it's limited to sets in Pascal, where its complexity is 
O(1).
Oct 28 2014
parent reply "Baz" <basile.burg gmx.com> writes:
On Tuesday, 28 October 2014 at 16:32:13 UTC, Marc Schütz wrote:

 On Tuesday, 28 October 2014 at 15:11:01 UTC, Baz wrote:

 On Tuesday, 28 October 2014 at 13:50:24 UTC, Nordlöw wrote:

 Has there been any proposals/plans to make operator "in" work 
 for elements in ranges such as

   assert('x' in ['x']);

 I'm missing that Python feature when I work in D.


 There is also something similar in Pascal, at the language 
 level. Very handy when working with characters or enums.


 AFAIR it's limited to sets in Pascal, where its complexity is 
 O(1).


If "in" is used as a syntactic sugar, e.g to call 
"std.algorithm.canFind" in a custom type, then why would the bigO 
be a concern ? To be clear, I was just trying to suggest that it 
can be done by writting from scratch some helpers structs.
Oct 28 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Tuesday, 28 October 2014 at 17:50:30 UTC, Baz wrote:

 On Tuesday, 28 October 2014 at 16:32:13 UTC, Marc Schütz wrote:

 On Tuesday, 28 October 2014 at 15:11:01 UTC, Baz wrote:

 On Tuesday, 28 October 2014 at 13:50:24 UTC, Nordlöw wrote:

 Has there been any proposals/plans to make operator "in" 
 work for elements in ranges such as

  assert('x' in ['x']);

 I'm missing that Python feature when I work in D.


 There is also something similar in Pascal, at the language 
 level. Very handy when working with characters or enums.


 AFAIR it's limited to sets in Pascal, where its complexity is 
 O(1).


 If "in" is used as a syntactic sugar, e.g to call 
 "std.algorithm.canFind" in a custom type, then why would the 
 bigO be a concern ?


It always was the argument against generalizing `in` to arrays. 
`in` is not alone in this respect. It's also expected that 
indexing and slicing be "cheap" operations.
Oct 28 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 28 October 2014 at 18:29:49 UTC, Marc Schütz wrote:

 It always was the argument against generalizing `in` to arrays. 
 `in` is not alone in this respect. It's also expected that 
 indexing and slicing be "cheap" operations.


BTW: Does anybody have an efficient unordered set container lying 
around somewhere?
Oct 28 2014
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 10/28/14 2:33 PM, "Nordlöw" wrote:

 On Tuesday, 28 October 2014 at 18:29:49 UTC, Marc Schütz wrote:

 It always was the argument against generalizing `in` to arrays. `in`
 is not alone in this respect. It's also expected that indexing and
 slicing be "cheap" operations.


 BTW: Does anybody have an efficient unordered set container lying around
 somewhere?


I haven't touched it in a LONG time, but dcollections has this (HashSet).

I don't claim that it's the most efficient however :)

https://github.com/schveiguy/dcollections/blob/master/dcollections/HashSet.d

-Steve
Oct 28 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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!
Oct 28 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Tuesday, 28 October 2014 at 18:29:49 UTC, Marc Schütz wrote:

 On Tuesday, 28 October 2014 at 17:50:30 UTC, Baz wrote:

 On Tuesday, 28 October 2014 at 16:32:13 UTC, Marc Schütz wrote:

 On Tuesday, 28 October 2014 at 15:11:01 UTC, Baz wrote:

 On Tuesday, 28 October 2014 at 13:50:24 UTC, Nordlöw wrote:

 Has there been any proposals/plans to make operator "in" 
 work for elements in ranges such as

 assert('x' in ['x']);

 I'm missing that Python feature when I work in D.


 There is also something similar in Pascal, at the language 
 level. Very handy when working with characters or enums.


 AFAIR it's limited to sets in Pascal, where its complexity is 
 O(1).


 If "in" is used as a syntactic sugar, e.g to call 
 "std.algorithm.canFind" in a custom type, then why would the 
 bigO be a concern ?


 It always was the argument against generalizing `in` to arrays. 
 `in` is not alone in this respect. It's also expected that 
 indexing and slicing be "cheap" operations.


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.
Oct 28 2014
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
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
Oct 28 2014
parent "Araq" <rumpf_a web.de> writes:
 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.
Oct 29 2014