digitalmars.D - D compile time algorithms implementation
- khurshid (24/24) Apr 19 2013 I just have read from github std.variant, std.typetuple, etc.
- bearophile (6/10) Apr 20 2013 I remember a very recent discussion in reddit.com/r/cpp about
- Peter Alexander (9/11) Apr 20 2013 I guess the simple answer is that their complexity hasn't been
- Walter Bright (2/6) Apr 20 2013 Yes, please do so.
- khurshid (3/11) Apr 21 2013 I just have create issue:
- Timon Gehr (4/27) Apr 20 2013 FWIW I think the O(N^2) behaviour is a limitation of the compiler
- khurshid (5/36) Apr 20 2013 For using only one algorithm - it's no problem.
- khurshid (1/1) Apr 20 2013 I wanted to say "NoDuplicates" ))
- Andrei Alexandrescu (5/6) Apr 22 2013 I'd say let's add bug reports (either for library, compiler, or both)
- khurshid (9/16) Apr 23 2013 Thanks for suggestion.
- khurshid (1/7) Apr 23 2013 Oh,god !!!
- khurshid (32/32) Apr 24 2013 Is this code right?
- David Nadlinger (4/7) Apr 24 2013 No. templateAnd/templateOr are documented to perform
- Timon Gehr (5/14) Apr 24 2013 I think that is what the implementation intends to do. I am more worried...
- Timon Gehr (4/20) Apr 24 2013 (Also, the lookup rules have been changed for function calls and
I just have read from github std.variant, std.typetuple, etc.
source codes.
And I have a question.
Why more linear algorithms implemented with O(N^2) ?
example: staticMap, it doesnot compiled more 500 arguments.
although, following version compiled for more than 32768
arguments:
template staticMap2(alias F, T...)
{
static if (T.length == 0)
{
alias TypeTuple!() staticMap2;
}
else static if (T.length == 1)
{
alias TypeTuple!(F!(T[0])) staticMap2;
}
else
{
alias TypeTuple!( staticMap2!(F, T[0..$/2]),
staticMap2!(F,
T[$/2..$])) staticMap2;
}
}
Apr 19 2013
"bearophile" <bearophileHUGS lycos.com> khurshid:I just have read from github std.variant, std.typetuple, etc. source codes. And I have a question. Why more linear algorithms implemented with O(N^2) ?I remember a very recent discussion in reddit.com/r/cpp about using this idea. I think very large tuples are not common. Bye, bearophile
Apr 20 2013
On Saturday, 20 April 2013 at 06:07:18 UTC, khurshid wrote:Why more linear algorithms implemented with O(N^2) ? example: staticMap, it doesnot compiled more 500 arguments.I guess the simple answer is that their complexity hasn't been given much thought, as I don't image they were intended to be used with that many arguments (of course, this is not an excuse). If possible, could you file an enhancement request? It would also be great if you could add your improvement as a pull request on github! http://d.puremagic.com/issues/enter_bug.cgi?product=D https://github.com/D-Programming-Language/phobos
Apr 20 2013
On 4/20/2013 2:27 AM, Peter Alexander wrote:If possible, could you file an enhancement request? It would also be great if you could add your improvement as a pull request on github! http://d.puremagic.com/issues/enter_bug.cgi?product=D https://github.com/D-Programming-Language/phobosYes, please do so.
Apr 20 2013
On Saturday, 20 April 2013 at 20:12:18 UTC, Walter Bright wrote:On 4/20/2013 2:27 AM, Peter Alexander wrote:I just have create issue: http://d.puremagic.com/issues/show_bug.cgi?id=9976If possible, could you file an enhancement request? It would also be great if you could add your improvement as a pull request on github! http://d.puremagic.com/issues/enter_bug.cgi?product=D https://github.com/D-Programming-Language/phobosYes, please do so.
Apr 21 2013
On 04/20/2013 08:07 AM, khurshid wrote:
I just have read from github std.variant, std.typetuple, etc. source
codes.
And I have a question.
Why more linear algorithms implemented with O(N^2) ?
example: staticMap, it doesnot compiled more 500 arguments.
although, following version compiled for more than 32768 arguments:
template staticMap2(alias F, T...)
{
static if (T.length == 0)
{
alias TypeTuple!() staticMap2;
}
else static if (T.length == 1)
{
alias TypeTuple!(F!(T[0])) staticMap2;
}
else
{
alias TypeTuple!( staticMap2!(F, T[0..$/2]),
staticMap2!(F,
T[$/2..$])) staticMap2;
}
}
FWIW I think the O(N^2) behaviour is a limitation of the compiler
implementation (I think ropes might be a better data structure than
arrays to back compiler tuples.)
Apr 20 2013
On Saturday, 20 April 2013 at 11:07:28 UTC, Timon Gehr wrote:On 04/20/2013 08:07 AM, khurshid wrote:For using only one algorithm - it's no problem. But if we are using algorithm inside another algorithm (like NoDuples(..) which inside uses EraseAll ) - compile time will become very slowly.I just have read from github std.variant, std.typetuple, etc. source codes. And I have a question. Why more linear algorithms implemented with O(N^2) ? example: staticMap, it doesnot compiled more 500 arguments. although, following version compiled for more than 32768 arguments: template staticMap2(alias F, T...) { static if (T.length == 0) { alias TypeTuple!() staticMap2; } else static if (T.length == 1) { alias TypeTuple!(F!(T[0])) staticMap2; } else { alias TypeTuple!( staticMap2!(F, T[0..$/2]), staticMap2!(F, T[$/2..$])) staticMap2; } }FWIW I think the O(N^2) behaviour is a limitation of the compiler implementation (I think ropes might be a better data structure than arrays to back compiler tuples.)
Apr 20 2013
On 4/20/13 8:41 AM, khurshid wrote:I wanted to say "NoDuplicates" ))I'd say let's add bug reports (either for library, compiler, or both) for each of these instances, and post pull requests appropriately. Thanks, Andrei
Apr 22 2013
On Monday, 22 April 2013 at 15:01:26 UTC, Andrei Alexandrescu wrote:On 4/20/13 8:41 AM, khurshid wrote:Thanks for suggestion. But, I'm sorry, I do not have the ability to work with the code itself, now. I take a few other things. Regards, Khursid.I wanted to say "NoDuplicates" ))I'd say let's add bug reports (either for library, compiler, or both) for each of these instances, and post pull requests appropriately. Thanks, Andrei
Apr 23 2013
But, I'm sorry, I do not have the ability to work with the code itself, now. I take a few other things. Regards, Khursid.Oh,god !!!
Apr 23 2013
Is this code right?
template templateAnd(Preds...)
{
template templateAnd(T...)
{
static if (Preds.length == 0)
{
enum templateAnd = true;
}
else static if (Preds.length == 1)
{
enum templateAnd = Instantiate!(Preds[0],T);
}
else
{
static if (Instantiate!(.templateAnd(Preds[0..$/2]),T))
{
enum templateAnd =
Instantiate!(.templateAnd(Preds[$/2..$]),T);
}
else
{
enum templateAnd = false;
}
}
}
}
here
template Instantiate(alias P, T...)
{
alias Instantiate = P!(T);
}
Apr 24 2013
On Wednesday, 24 April 2013 at 08:46:03 UTC, khurshid wrote:
Is this code right?
template templateAnd(Preds...)
{ … }
No. templateAnd/templateOr are documented to perform
short-circuit evaluation of the operands.
David
Apr 24 2013
On 04/24/2013 09:28 PM, David Nadlinger wrote:On Wednesday, 24 April 2013 at 08:46:03 UTC, khurshid wrote:I think that is what the implementation intends to do. I am more worried about the expressions reading similar to: .templateAnd(Preds[0..$/2]) The code appears to be entirely untested.Is this code right? template templateAnd(Preds...) { … }No. templateAnd/templateOr are documented to perform short-circuit evaluation of the operands. David
Apr 24 2013
On 04/24/2013 10:28 PM, Timon Gehr wrote:On 04/24/2013 09:28 PM, David Nadlinger wrote:(Also, the lookup rules have been changed for function calls and template instantiations on eponymous template symbols, and therefore the '.' prefix is not needed anymore.)On Wednesday, 24 April 2013 at 08:46:03 UTC, khurshid wrote:I think that is what the implementation intends to do. I am more worried about the expressions reading similar to: .templateAnd(Preds[0..$/2]) The code appears to be entirely untested.Is this code right? template templateAnd(Preds...) { … }No. templateAnd/templateOr are documented to perform short-circuit evaluation of the operands. David
Apr 24 2013
I am newbie D language. Only, I am playing with meta programming. I have a question. Using D language futures, could to implement NoDuplicates meta algorithm with O(N) time, or though O(N ln(N) )?
Apr 24 2013
And, what to you're saying about that, MostDerived implementation? http://d.puremagic.com/issues/show_bug.cgi?id=9976
Apr 24 2013