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;
        }
}

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

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

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.)

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.

I wanted to  say "NoDuplicates" ))

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.

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

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

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.