Sử dụng lũy ​​thừa ** 0,5 kém hiệu quả hơn math.sqrt?

Question

Một câu nói từ "Python Programming: An Introduction to Computer Science"

Chúng ta có thể đưa ra những căn bậc hai sử dụng lũy ​​thừa **. Sử dụng math.sqrt có phần hiệu quả hơn.

"Hơi", nhưng ở mức độ nào và như thế nào?

Answer 1

Về mặt lý thuyết, hammar's answer và duffymo's answer là các dự đoán tốt. Nhưng trong thực tế, trên máy tính của tôi, đó là không hiệu quả hơn:

>>> import timeit 
>>> timeit.timeit(stmt='[n ** 0.5 for n in range(100)]', setup='import math', number=10000) 
0.15518403053283691 
>>> timeit.timeit(stmt='[math.sqrt(n) for n in range(100)]', setup='import math', number=10000) 
0.17707490921020508 

Một phần của vấn đề là các hoạt động .. Nếu bạn nhập sqrt trực tiếp vào không gian tên, bạn sẽ nhận được một chút cải thiện.

>>> timeit.timeit(stmt='[sqrt(n) for n in range(100)]', setup='from math import sqrt', number=10000) 
0.15312695503234863 

Từ khóa có: nhẹ.

Kiểm tra thêm cho thấy rằng khi số càng lớn, lợi ích bạn nhận được từ việc sử dụng số tăng sqrt tăng. Nhưng vẫn không nhiều!

>>> timeit.timeit(stmt='[n ** 0.5 for n in range(1000000)]', setup='import math', number=1) 
0.18888211250305176 
>>> timeit.timeit(stmt='[math.sqrt(n) for n in range(1000000)]', setup='import math', number=1) 
0.18425297737121582 
>>> timeit.timeit(stmt='[sqrt(n) for n in range(1000000)]', setup='from math import sqrt', number=1) 
0.1571958065032959 

Answer 2

** phải hỗ trợ mọi số mũ trong khi math.sqrt biết luôn luôn là 0.5. Do đó, math.sqrt có thể sử dụng thuật toán chuyên biệt hơn (và do đó có thể hiệu quả hơn).

Answer 3

Tôi đoán rằng math.sqrt sử dụng Newton's method, hội tụ bậc hai và lũy thừa sử dụng thứ khác chậm hơn.

Answer 4

Không cần phải đoán việc triển khai, chúng tôi có thể đọc mã!

math.sqrt là một wrapper mỏng về sqrt từ thư viện C chuẩn: xem mathmodule.c, line 956

Nhà điều hành ** có nhiều triển khai tùy thuộc vào loại của các đối số, nhưng trong trường hợp của một số mũ dấu chấm động, nó cuối cùng gửi đến pow từ thư viện C chuẩn (xem floatobject.c line 783).

Các CPU hiện đại thường có các lệnh căn bậc hai đặc biệt mà các quy trình lũy thừa chung không sử dụng (so sánh và đối chiếu các triển khai pow và sqrt trong glibc cho x86-64). Nhưng một khi tất cả chi phí thông dịch được thêm vào (mã byte, kiểm tra kiểu, công văn vv), sự khác biệt về tốc độ thô không quan trọng lắm, và có thể bị chi phối bởi các vấn đề như bạn gọi trực tiếp hoặc tra cứu thông qua số sqrt mô-đun math (như được hiển thị bằng thời gian trong các câu trả lời khác).

Answer 5

Đây là cách tiếp cận hơi khác. Chúng tôi muốn một int chỉ lớn hơn căn bậc hai. Hai cách (không đồng ý với số vuông nhưng đó là OK):

>>>timeit.timeit(stmt='[int(n**0.5)+1 for n in range(1000000)]', setup='', number=1) 
0.481772899628 
>>>timeit.timeit(stmt='[ceil(sqrt(n)) for n in range(1000000)]', setup='from math import sqrt, ceil', number=1) 
0.293844938278 
>>>timeit.timeit(stmt='[int(ceil(sqrt(n))) for n in range(1000000)]', setup='from math import sqrt, ceil', number=1) 
0.511347055435 

Vì vậy, các hàm toán học sẽ nhanh hơn ... cho đến khi bạn chuyển phao sang int.(Tôi cần phải làm rất nhiều so sánh với giá trị, và trong khi tôi đã không thử nghiệm nó, so sánh các số nguyên nên rẻ hơn so sánh nổi.)

Nhưng hey, nó là Python. Bạn đang trên đầu trang của quá nhiều abstractions để cố gắng tối ưu hóa hiệu suất với mức độ chi tiết này.