www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D compile time algorithms implementation

reply "khurshid" <khurshid.normuradov gmail.com> writes:
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;
         }
}
Apr 19 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Apr 20 2013
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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
Apr 20 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Apr 20 2013
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.)
Apr 20 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Apr 22 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Apr 24 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
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.)
Apr 24 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
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.
Apr 20 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
I wanted to  say "NoDuplicates" ))
Apr 20 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
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
Apr 21 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
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.
Apr 23 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
 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 !!!
Apr 23 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
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);
    }
Apr 24 2013
prev sibling next sibling parent "David Nadlinger" <see klickverbot.at> writes:
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
Apr 24 2013
prev sibling next sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
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) )?
Apr 24 2013
prev sibling parent "khurshid" <khurshid.normuradov gmail.com> writes:
And, what to you're saying about that, MostDerived implementation?
http://d.puremagic.com/issues/show_bug.cgi?id=9976
Apr 24 2013