编译时函数的记忆

Question

我想懒惰地计算函数。由于计算 return 值很昂贵，我必须使用记忆，尤其是对于被调用的子函数，否则计算的时间复杂度呈指数级增长。我需要编译时的结果。（我正在编写一个库，它根据提供的字符串提供各种编译时模板。）所以简而言之，我需要在编译时进行记忆。

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

它不完全是记忆，但它可能足以满足您的需要 - 请注意，如果您评论其中一个 sumMany，编译时间是相同的。

编译时函数的记忆

Memoization for compile time functions

d

memoization

compilation-time

ctfe