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.