Cách tăng hiệu suất để ước tính `Pi`in Python

Question

Tôi đã viết mã sau bằng Python, để ước tính giá trị của Pi. Nó được gọi là phương pháp Monte Carlo. Rõ ràng bằng cách tăng số lượng mẫu mã trở nên chậm hơn và tôi giả định rằng phần chậm nhất của mã nằm trong phần lấy mẫu. Tôi làm cách nào để nhanh hơn?

from __future__ import division 
import numpy as np 

a = 1 
n = 1000000 

s1 = np.random.uniform(0,a,n) 
s2 = np.random.uniform(0,a,n) 

ii=0 
jj=0 

for item in range(n): 
    if ((s1[item])**2 + (s2[item])**2) < 1: 
     ii = ii + 1 

print float(ii*4/(n)) 

Bạn có đề xuất mã khác (có lẽ là nhanh hơn) không?

Answer 1

Nút cổ chai ở đây thực sự là vòng lặp for của bạn. Python for vòng là tương đối chậm, vì vậy nếu bạn cần phải lặp lại hơn một triệu mục, bạn có thể đạt được rất nhiều tốc độ bằng cách tránh chúng hoàn toàn. Trong trường hợp này, nó khá dễ dàng. Thay vì điều này:

for item in range(n): 
    if ((s1[item])**2 + (s2[item])**2) < 1: 
     ii = ii + 1 

làm điều này:

ii = ((s1 ** 2 + s2 ** 2) < 1).sum() 

này hoạt động vì numpy đã xây dựng-in hỗ trợ cho các hoạt động mảng tối ưu. Việc lặp xảy ra trong c thay vì python, vì vậy nó nhanh hơn nhiều. Tôi đã thực hiện một bài kiểm tra nhanh để bạn có thể thấy sự khác biệt:

>>> def estimate_pi_loop(x, y): 
...  total = 0 
...  for i in xrange(len(x)): 
...   if x[i] ** 2 + y[i] ** 2 < 1: 
...    total += 1 
...  return total * 4.0/len(x) 
... 
>>> def estimate_pi_numpy(x, y): 
...  return ((x ** 2 + y ** 2) < 1).sum() 
... 
>>> %timeit estimate_pi_loop(x, y) 
1 loops, best of 3: 3.33 s per loop 
>>> %timeit estimate_pi_numpy(x, y) 
100 loops, best of 3: 10.4 ms per loop 

Dưới đây là một vài ví dụ về các loại hoạt động có thể, để bạn hiểu cách hoạt động của nó.

Squaring một mảng:

>>> a = numpy.arange(5) 
>>> a ** 2 
array([ 0, 1, 4, 9, 16]) 

mảng Thêm:

>>> a + a 
array([0, 2, 4, 6, 8]) 

mảng So sánh:

>>> a > 2 
array([False, False, False, True, True], dtype=bool) 

Tổng giá trị boolean:

>>> (a > 2).sum() 
2 

Như bạn có thể nhận ra, có những cách nhanh hơn để ước tính Pi, nhưng tôi sẽ thừa nhận rằng tôi luôn ngưỡng mộ sự đơn giản và hiệu quả của phương pháp này.

Answer 2

Bạn đã chỉ định mảng có nhiều mảng, vì vậy bạn nên sử dụng những lợi ích đó cho lợi thế của mình.

for item in range(n): 
    if ((s1[item])**2 + (s2[item])**2) < 1: 
     ii = ii + 1 

trở thành

s1sqr = s1*s1 
s2sqr = s2*s2 
s_sum = s1sqr + s2sqr 
s_sum_bool = s_sum < 1 
ii = s_sum_bool.sum() 
print float(ii*4/(n)) 

Trong trường hợp bạn đang bình phương các mảng, tổng hợp chúng, kiểm tra nếu tổng là ít hơn 1 và sau đó tổng hợp các giá trị boolean (false = 0, đúng = 1) để có được tổng số đáp ứng tiêu chí.

Answer 3

Tôi upvoted câu trả lời senderle 's, nhưng trong trường hợp bạn không muốn thay đổi mã của bạn quá nhiều:

numba là một thư viện được thiết kế cho mục đích này.

Chỉ cần xác định thuật toán của bạn như là một chức năng, và thêm @jit trang trí:

from __future__ import division 
import numpy as np 
from numba import jit 

a = 1 
n = 1000000 

s1 = np.random.uniform(0,a,n) 
s2 = np.random.uniform(0,a,n) 

@jit 
def estimate_pi(s1, s2): 
    ii = 0 
    for item in range(n): 
     if ((s1[item])**2 + (s2[item])**2) < 1: 
      ii = ii + 1 
    return float(ii*4/(n)) 

print estimate_pi(s1, s2) 

Mở máy tính xách tay của tôi, nó đạt khoảng một tăng tốc 20x cho n = 100000000, và sự tăng tốc 3x cho n = 1000000.