Tại sao hiệu quả tương đối của các thói quen này trong Mathematica?

Question

Tôi đã ngạc nhiên bởi một sự khác biệt về thời gian mà Daniel Lichtblau pointed out theo hai cách để có được sự khác biệt giữa số nguyên tố (PrimeOmega) và số nguyên tố riêng biệt (PrimeNu) của một số nguyên, n. Vì vậy, tôi quyết định xem xét nó thêm một chút.

Các chức năng g1 và g2 dưới đây là các biến thể nhỏ của ones Daniel được sử dụng cũng như ba loại khác. Tất cả chúng đều trả về số lượng các số nguyên không có hình vuông từ 1 đến n. Nhưng sự khác biệt khá ấn tượng. Bất cứ ai có thể giải thích lý do đằng sau sự khác biệt. Cụ thể, tại sao Sum trong g5 mang lại lợi thế về tốc độ như vậy?

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]}] 

Việc so sánh:

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

Kết quả:

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

---

Edit:

Mysticial đưa ra khả năng rằng ro sau utines đã gặt hái những lợi ích của thứ tự của họ - rằng một số bộ nhớ đệm có thể đã xảy ra.

Vì vậy, chúng ta hãy chạy so sánh theo thứ tự ngược lại:

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

Kết quả so sánh ngược lại:

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

Dự đoán: Một đoán hợp lý, nhưng không được hỗ trợ bởi dữ liệu.

Answer 1

ModebiusMu cho số nhỏ có một số mã rây nhanh chuyên dụng có hiệu lực phím tắt thực sự yếu tố, chỉ cần đếm khi nó tìm thấy các yếu tố. Nó sẽ không thêm số mũ như PrimeOmega vì vậy nó thực sự có ít nhiệm vụ hơn. Ngoài ra nó có thể ngắn mạch bất cứ khi nào nó phát hiện một yếu tố chính với đa dạng.

Tôi tin rằng điểm ngắt là trùng hợp, khoảng 2^20. Không có thời gian để kiểm tra nhưng nó thực sự có thể chậm hơn một chút.

Câu trả lời đó cho g4. Rõ ràng g5 đang sử dụng sự thông minh trên một phần của lập trình viên (không có gì sai với điều đó tất nhiên), do đó đạt được tốc độ.

Đối với g3, đó thực chất là cuộc gọi đến g4 về mặt mã thực hiện. Các nút cổ chai, trong trường hợp này, là tiền xử lý trên không vì nó được thực hiện trong mathematica chứ không phải là mã C. Tôi nghi ngờ điều này sẽ ít có thể nhìn thấy nếu đầu vào lớn hơn đã được sử dụng, vì trong trường hợp như vậy nhiều thời gian hơn sẽ được chi tiêu làm công việc thực tế hơn là trong phí thông dịch Mathematica. Một lần nữa, tôi đã không thử nghiệm này.