D compile time algorithms implementation

Timon Gehr timon.gehr at gmx.ch
Sat Apr 20 04:07:27 PDT 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.)



More information about the Digitalmars-d mailing list