Python使数学计算更快

Question

我有这个代码来查找毕达哥拉斯三元组，它工作得很好。我只是想让它快点。在我的Intel i5 1135G7上，大约需要0.1272754669189453时间。也许可以使用multiprocessing模块来完成，因为我的CPU利用率不是100%。

import math
import time 

results = [] 
start_time = time.time()
def triplets4(n):
for a in range(n):
for b in range(a, n):
c = math.sqrt(a * a + b * b) 
if c.is_integer() and c<=n:
results.append([a , b, int(c)])
triplets4(1000)
end_time = time.time()
for x in results:
print(x)
print(end_time-start_time) #print time elapsed

Answer 1

我不是python程序员，但在观察了一些机会后，我想我会为性能优化做一些修改。除了使用优化的库函数外，Python不是一种非常适合用于提高速度的语言。您需要一个可以编译的脚本来提高性能。多线程可以使程序更快，但通常需要对代码进行重大重构。我从输出中排除了a=0，因为我认为它们不算作三元组。无论如何，这就是我所做的，即使从脚本中删除a=0，在我的计算机上运行速度也要快20%。虽然性能提高不是很大，但我认为可以从我所做的更改中吸取一些教训。

import math
import time 

results = [] 
start_time = time.time()
def triplets4(n):
n2 = n*n
for a in range(1, n):
a2 = a*a
blim = 1+int(math.sqrt(n2 - a2))
for b in range(a+1, blim):
arg = a2 + b * b
c = math.sqrt(arg) 
if c.is_integer():
results.append([a , b, int(c)])
triplets4(1000)
end_time = time.time()
for x in results:
print(x)
print(end_time-start_time) #print time elapsed 

Answer 2

简短回答

一个简单的方法是在运行sqrt或is_integer之前添加对(a * b) % 12 != 0的检查。

根据Wolfram关于毕达哥拉斯三元组的页面，毕达哥拉斯三元组/三角形的腿(a和b)的乘积总是能被12整除。

长回答

我们应该首先分析你的代码。为了简单起见，我删除了print语句和计时器，所以我们使用这个版本的代码:

import math
results = [] 
def triplets4(n):
for a in range(n):
for b in range(a, n):
c = math.sqrt(a * a + b * b) 
if c.is_integer() and c<=n:
results.append([a , b, int(c)])
triplets4(1000)

使用cProfile:

python -m cProfile .pythagorean.py      
1002950 function calls in 0.270 seconds
Ordered by: cumulative time
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    0.270    0.270 {built-in method builtins.exec}
1    0.000    0.000    0.270    0.270 pythagorean.py:1(<module>)
1    0.175    0.175    0.269    0.269 pythagorean.py:5(triplets4)
500500    0.051    0.000    0.051    0.000 {built-in method math.sqrt}
500500    0.043    0.000    0.043    0.000 {method 'is_integer' of 'float' objects}
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:1167(_find_and_load)
1881    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}

大部分时间花在math.sqrt和is_integer上。

因此，为了提高代码的速度，我们应该少调用这些函数。

我能想到的最简单的方法是可除性测试。

import math
results = [] 
def triplets4(n):
for a in range(n):
for b in range(a, n):
# product of legs must be divisible by 12
if (a * b) % 12 != 0: continue
c = math.sqrt(a * a + b * b) 
if c.is_integer() and c<=n:
results.append([a , b, int(c)])
triplets4(1000)

python -m cProfile .pythagorean_v2.py
280672 function calls in 0.174 seconds
Ordered by: cumulative time
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    0.174    0.174 {built-in method builtins.exec}
1    0.000    0.000    0.174    0.174 pythagorean_v2.py:1(<module>)
1    0.135    0.135    0.174    0.174 pythagorean_v2.py:5(triplets4)
139361    0.021    0.000    0.021    0.000 {built-in method math.sqrt}
139361    0.018    0.000    0.018    0.000 {method 'is_integer' of 'float' objects}
1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:1167(_find_and_load)
1881    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}

在两个版本中，我们仍然添加了相同数量的三元组(1881)，所以这是一个好兆头。