为什么Mathematica中这些例程的相对效率？

Question

我对Daniel Lichtblau 以两种方式指出的时间差异感到惊讶,以便得出素数因子(PrimeOmega)的数量与PrimeNu整数n 的不同素数因子()的数量之间的差异.所以我决定再深入研究一下.

的功能g1和g2下面是的轻微变化那些丹尼尔使用以及其他三个.它们都返回从1到n的无平方整数的数量.但差异相当大.任何人都可以解释差异背后的原因.特别是,为什么Sum在g5提供这样的速度优势？

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解释器开销.我再次测试过这个问题.