Mathematicaでのこれらのルーチンの相対効率はなぜなのでしょうか？

Question

Daniel Lichtblau pointed outは、素因数（PrimeOmega）の数と整数nの別個の素因数（PrimeNu）の数の違いを得る2通りの方法でタイミングの違いに驚いた。だから私はもう少しそれを調べることにした。

以下の機能g1およびg2は、ダニエルと他の3つの使用された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]] 

結果：Mysticial後者ROという可能性を提起

：

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

---

編集utineは注文のメリットを享受していました。つまり、キャッシュが行われている可能性があります。

それでは、逆の順序で比較を実行してみましょう：逆転比較の

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を呼び出します。この場合のボトルネックは、Cコードではなく数学的に実装されているため、前処理オーバーヘッドです。このような場合、Mathematicaインタプリタのオーバーヘッドではなく、実際の作業に費やす時間が増えるため、より多くの入力が使用された場合、これは目に見えないものと思われます。繰り返しますが、私はこれをテストしていません。