D compile time algorithms implementation
khurshid
khurshid.normuradov at gmail.com
Sat Apr 20 05:35:30 PDT 2013
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.
More information about the Digitalmars-d
mailing list