Re: More uses of operator in
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.
Re: More uses of operator in
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.
More uses of operator in
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.
Re: More uses of operator in
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
Re: More uses of operator in
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] );
}
Re: More uses of operator in
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.
Re: More uses of operator in
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).
Re: More uses of operator in
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.
Re: More uses of operator in
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.
Re: More uses of operator in
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?
Re: More uses of operator in
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.
Re: More uses of operator in
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
Re: More uses of operator in
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.
Re: More uses of operator in
On 10/28/14 3:45 PM, Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?=
ola.fosheim.grostad+dl...@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
Re: More uses of operator in
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
Re: More uses of operator in
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!
