Divide & Conquer divides, but doesn't conquer
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Mon May 25 03:10:57 UTC 2020
On 5/24/20 10:32 PM, Steven Schveighoffer wrote:
> On 5/24/20 9:48 PM, Andrei Alexandrescu wrote:
>> Another one:
>>
>> template Filter(alias pred, TList...)
>> {
>> static if (TList.length == 0)
>> {
>> alias Filter = AliasSeq!();
>> }
>> else static if (TList.length == 1)
>> {
>> static if (pred!(TList[0]))
>> alias Filter = AliasSeq!(TList[0]);
>> else
>> alias Filter = AliasSeq!();
>> }
>> else
>> {
>> alias Filter =
>> AliasSeq!(
>> Filter!(pred, TList[ 0 .. $/2]),
>> Filter!(pred, TList[$/2 .. $ ]));
>> }
>> }
>>
>> Why cut the problem size in half if it doesn't improve complexity?
>
> Because it doesn't work for large sets unless you do this.
>
> If you do a "linear" recursive template, it fails after about 1000
> levels. A divide-and-conquer will not get that deep.
>
> So in essence, it's a solution for a compiler restriction, not for
> performance.
>
> -Steve
I see, thanks.
More information about the Digitalmars-d
mailing list