为什么递归阶乘比锡兰的折叠更快

Question

我有这个锡兰代码：

Integer fact(Integer n)
{
    return (n<=1)then 1 else n*fact(n-1);
}
Integer? factorial(Integer|String|Null n)
{
    Integer? num;
    if(is String n)
    {
        num=parseInteger(n);
    }
    else if(is Integer n)
    {
        num=n;      
    }   
    else
    {
        num=null;
    }
    if(exists num)
    {
        if(num<0)
        {
            return null;
        }
        if(num==0)
        {
            return 1;
        }
        return (2..num).fold(1)((x,y)=>x*y);//line 1
    }
    else
    {
        return null;        
    }       
}
shared void main() 
{
    print("enter a number");
    value input=process.readLine()?.trimmed;
    value starttime=system.milliseconds;
    value fact=factorial(input);
    value elapsedtime=(system.milliseconds-starttime).float/1000;
    if(exists fact)
    {
        print("(!n)=``fact``");
        print(elapsedtime);
    }
    else
    {
        print("Error, either you gave a negative number or you didn't enter an integer(or did you left the input blank ?)");
    }   
}

在第 1 行，我使用 fold 来计算阶乘，我得到的性能在 0.08 到 0.06 秒之间。

现在，如果我用这个替换第 1 行：

return fact(num);

我的性能介于 0.021 和 0.012 之间，这是为什么？

在这种情况下，我尝试的数字是 10。

Answer 1

先说几句：

不要使用 system.milliseconds 进行小的测量，这是出了名的不精确（它的最大分辨率是 1/60 秒或大约 16 毫秒），请改用 system.nanoTime
对于 Java VM，这是一个太小的基准测试，无法说出任何有价值的东西，VM 在进行任何优化之前需要 "warm up"。有关详细信息，请参阅 How do I write a correct micro-benchmark in Java?

但除此之外，fact() 可能更快的一个原因是因为它的代码在内部得到优化以使用 Java 基本类型，而 fold() 是一个通用函数，这可能意味着很多拳击比赛正在进行。

目前，Ceylon 在处理 Integer 和 Float 等基本类型时，还不太擅长优化具有泛型参数或 return 类型的函数。希望在未来的版本中我们将能够对此进行一些补救。

为什么递归阶乘比锡兰的折叠更快

why recursive factorial is faster than fold in ceylon

performance

ceylon