performance - 为什么这些例程在 Mathematica 中的相对效率高？

Question

我对 Daniel Lichtblau pointed out 的时间差异感到惊讶以两种方式获取整数 n 的素数 (PrimeOmega) 与不同素数 (PrimeNu) 之间的差异。所以我决定进一步研究一下。

下面的函数 g1 和 g2 是 ones 的细微变化。丹尼尔和其他三个人一样使用过。它们都返回从 1 到 n 的无平方整数的数量。但差异相当显着。任何人都可以解释差异背后的原因。特别是，为什么 g5 中的 Sum 提供这样的速度优势？

g1[n_] := Count[PrimeOmega[Range[n]] - PrimeNu[Range[n]], 0]

g2[n_] := Count[With[{fax = FactorInteger[#]}, 
 Total[fax[[All, 2]]] - Length[fax]] & /@ Range[n], 0]

g3[n_] := Count[SquareFreeQ/@ Range[n], True]

(* g3[n_] := Count[SquareFreeQ[#] & /@ Range[n], True] Mr.Wizard's suggestion
   incorporated above. Better written but no significant increase in speed. *) 

g4[n_] := n - Count[MoebiusMu[Range[n]], 0]

g5[n_] := Sum[MoebiusMu[d]*Floor[(n - 1)/d^2], {d, 1, Sqrt[n - 1]}]  

比较:

n = 2^20;
Timing[g1[n]]
Timing[g2[n]]
Timing[g3[n]]
Timing[g4[n]]
Timing[g5[n]]

结果:

{44.5867, 637461}
{11.4228, 637461}
{4.43416, 637461}
{1.00392, 637461}
{0.004478, 637461}

---

编辑:

Mysticial 提出了后一种例程正在从它们的顺序中获益的可能性——某些缓存可能一直在进行。

所以让我们以相反的顺序运行比较:

n = 2^20;
Timing[g5[n]]
Timing[g4[n]]
Timing[g3[n]]
Timing[g2[n]]
Timing[g1[n]]

反向比较结果:

{0.003755, 637461}
{0.978053, 637461}
{4.59551, 637461}
{11.2047, 637461}
{44.5979, 637461}

结论:合理的猜测，但数据不支持。

Answer 1

用于较小数字的 ModebiusMu 有一些专用的快速筛选代码，实际上可以缩短实际的因式分解，只在找到因子时进行计数。它不会像 PrimeOmega 那样添加指数，因此它的任务确实较少。每当它检测到具有多重性的质因数时，它也可以短路。

我相信临界点巧合地在 2^20 左右。没有时间测试，但它确实可能会变慢一点。

这就是 g4 的答案。显然，g5 在程序员方面发挥了聪明才智(当然这没有错)，因此速度提高了。

至于g3，在实现代码上，本质上是对g4的调用。在这种情况下，瓶颈是预处理开销，因为它是在 Mathematica 而不是 C 代码中实现的。我怀疑如果使用更大的输入，这将不太明显，因为在这种情况下，更多的时间将花在做真正的工作上，而不是花在 Mathematica 解释器开销上。同样，我还没有对此进行测试。