Re: D compile time algorithms implementation
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) )?
Re: D compile time algorithms implementation
And, what to you're saying about that, MostDerived implementation? http://d.puremagic.com/issues/show_bug.cgi?id=9976
Re: D compile time algorithms implementation
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 !!!
Re: D compile time algorithms implementation
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);
}
Re: D compile time algorithms implementation
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
Re: D compile time algorithms implementation
On 04/24/2013 10:28 PM, Timon Gehr wrote:
On 04/24/2013 09:28 PM, David Nadlinger wrote:
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
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.
(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.)
Re: D compile time algorithms implementation
On 04/24/2013 09:28 PM, David Nadlinger wrote:
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
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.
Re: D compile time algorithms implementation
On Monday, 22 April 2013 at 15:01:26 UTC, Andrei Alexandrescu wrote: 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 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.
Re: D compile time algorithms implementation
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
Re: D compile time algorithms implementation
On Saturday, 20 April 2013 at 20:12:18 UTC, Walter Bright wrote: 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/phobos Yes, please do so. I just have create issue: http://d.puremagic.com/issues/show_bug.cgi?id=9976
D compile time algorithms implementation
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;
}
}
Re: D compile time algorithms implementation
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
Re: D compile time algorithms implementation
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
Re: D compile time algorithms implementation
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.)
Re: D compile time algorithms implementation
On Saturday, 20 April 2013 at 11:07:28 UTC, Timon Gehr wrote:
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.)
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.
Re: D compile time algorithms implementation
I wanted to say NoDuplicates ))
Re: D compile time algorithms implementation
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/phobos Yes, please do so.
