编译时函数的记忆

Question

我想懒洋洋地评估函数.由于计算返回值很昂贵,我必须使用memoization,特别是对于被调用的子函数,否则计算的时间复杂度会呈指数级爆炸.我需要在编译时得到结果.(我正在编写一个库,根据提供的字符串提供各种编译时模板.)简而言之,我需要在编译期间进行memoization.

std.functional.memoize不起作用CT,所以这是不可能的.DMD和LDC不够聪明,不能记住纯函数,至少这是我对简单纯函数的实验结果:我测试它是否缓存结果:

使用简单的参数:

int sumN(int n) pure {
    int result = 0;
    for (int i = 0; i<=n; i++) result += i;
    return result;
}

void main() {
    enum sumMany =    sumN(2000000);
    enum sumMany2 =   sumN(2000000);
    writeln(sumMany, " ", sumMany2);
}

使用模板参数:

int sumN(int n)() pure {
    int result = 0;
    for (int i = 0; i<=n; i++) result += i;
    return result;
}

void main() {
    enum sumMany =    sumN!2000000;
    enum sumMany2 =   sumN!2000000;
    writeln(sumMany, " ", sumMany2);
}

定时编译(调用sumN一次vs两次):

time dmd -O -release -inline -boundscheck=off repeatpure.d

要么

time ldc2 -O5 -release -inline -boundscheck=off repeatpure.d

当我在源代码中有两个枚举时,编译时间总是两倍.

有没有办法记忆CT功能？

Answer 1

具有所有相同参数的模板应仅实例化一次,因此您要做的是在模板本身内使结果成为常量值(在本例中为枚举).

您的模板参数函数只会被实例化一次,但每次执行它都会运行.创建一个只运行一次的辅助函数:

template sumN(int n) {
    int helper() {
        int result = 0;
        for (int i = 0; i<=n; i++) result += i;
        return result;
    }

    // this is run once per unique argument group
    enum sumN = helper();
}

void main() {
    // so both of these now reference the same constant
    enum sumMany =    sumN!2000000;
    enum sumMany2 =   sumN!2000000;
    writeln(sumMany, " ", sumMany2);
}

它并不完全是memoization,但它可能足以满足您的需求 - 请注意,如果您对其中一个sumMany进行评论,编译时间是相同的.