使用 Python 尽快从 Madhava–Leibniz 系列中获得子序列 [英] Subsequence from Madhava–Leibniz series as fast as possible with Python
问题描述
Madhava–Leibniz 系列:我只需要创建一个从元素 k 到元素 n 的子序列:从这个系列中尽快创建和返回.
Madhava–Leibniz series: All I need is to create a subsequence from element k to element n: from this series to be created and returned as fast as possible.
我从 'leibniz' 单行函数开始,然后通过反复试验的方法一步一步地向 'madhava' 函数迈进,它的速度快了两倍.
I started from 'leibniz' one-liner function and step by step with the method of trial and error worked my way to 'madhava' function, which is twice faster.
更新:感谢 Andrej Kesely 的建议和两个破纪录的函数:madhava_leibniz"(比之前的记录提高 20%)和madhava_leibniz_starmap"(另一个15%).
UPDATE: Thanks to suggestions from Andrej Kesely and two record-breaking functions: 'madhava_leibniz' (20% improvement from the previous record) and 'madhava_leibniz_starmap' (another 15%).
最快的时间现在属于一个新函数madhava_leibniz".这比第一个leibniz"版本快 2.8 倍!
The fastest time now belongs to a new function 'madhava_leibniz'. That is a 2.8 faster than the first 'leibniz' version!
我的脚本现在的输出:
('3', '7', '3')
macOS version 10.14.5
Darwin-18.6.0-x86_64-i386-64bit
Python ('v3.7.3:ef4ec6ed12', 'Mar 25 2019 16:52:21') Clang 6.0 (clang-600.0.57)
Executing in 64bit
chunks * elements = m * n = 4 * 25,000,000 = 100,000,000
Time Pi 3.141592653589793 Error of calculation function
21.997 3.141592643589326 1.0000467121074053e-08 leibniz
11.489 3.141592643589326 1.0000467121074053e-08 madhava
9.269 3.141592643589326 1.0000467121074053e-08 madhava_leibniz
7.834 3.141592643589326 1.0000467121074053e-08 madhava_leibniz_starmap
时间以秒为单位.
我为块的数量选择了 4,所以稍后我可以针对多处理/多线程优化这些函数.n=250_000_000,但我建议在调试时设置 n=25_000_000 以缩短测试时间
I selected 4 for numbers of chunks, so later I can optimize these function for multiprocessing/multithreading. n=250_000_000, but I suggest set n=25_000_000 during debugging for a shorted testing time
Pi 计算和精度仅用于测试创建的子序列.时间是最重要的.
Pi calculation and precision are just for testing of created subsequences. Time is what important.
我仍在学习 Python,可能错过了一些使其更快的方法.你能推荐一个比madhava_leibniz"更快的版本吗?
I am still learning Python and maybe missed some way of making it even faster. Could you suggest a version faster than 'madhava_leibniz'?
脚本:
import math
import time
import platform
import sys
from itertools import cycle, starmap
from operator import truediv
# Functions with '*leibniz*' name must be Pythonic stanza (one-liner)
# but the statement can span multiple lines if over "Maximum Line Length"
# [79 characters in PEP 8 -- Style Guide for Python Code]
def madhava_leibniz_starmap(k, n):
return starmap(truediv, zip(cycle([1, -1] if k & 1 else [1, -1]),
range(2*k+1, 2*n+2, 2)))
def madhava_leibniz(k, n):
return [s / d for s, d in zip(cycle([1, -1] if k & 1 else [1, -1]),
range(2*k+1, 2*n+2, 2))]
def leibniz(k, n):
return [[1.0, -1.0][i % 2] / (2 * i + 1) for i in range(k, n+1)]
# Functions without '*leibniz*' but with 'madhava' pattern in the name are
# optimized for speed any way you like. Can be multiple statements.
def madhava(k, n):
series = [0.0] * (n - k + 1)
first_divisor = 2 * k + 1
last_divisor_plus_1 = 2 * n + 2
i = 0
if k & 1:
for divisor in range(first_divisor, last_divisor_plus_1, 4):
series[i] = -1 / divisor
i += 2
i = 1
for divisor in range(first_divisor + 2, last_divisor_plus_1, 4):
series[i] = 1 / divisor
i += 2
else:
for divisor in range(first_divisor, last_divisor_plus_1, 4):
series[i] = 1 / divisor
i += 2
i = 1
for divisor in range(first_divisor + 2, last_divisor_plus_1, 4):
series[i] = -1 / divisor
i += 2
return series
def report(function, m, n): # Test a function: time and values in data series
t = time.time()
series = []
for i in range(m):
series += function(i * n, (i + 1) * n - 1)
p = sum(series) * 4.0
print('{:6.3f}{:19.15f} {} {}'.format(time.time() - t, p, math.pi-p,
function.__name__))
if len(series) != n * m:
print('Error! actual length {}, requested {}'.format(len(series), n*m))
exit(1)
sign = [1.0, -1.0]
for i, a in enumerate(series):
e = sign[i % 2] / (2*i + 1)
if a != e:
print('Error! @ {} actual value {}, expected {}'.format(i, a, e))
exit(1)
if __name__ == '__main__': # Testing ... #####################################
def main():
print(platform.node())
(mac_ver, _, _) = platform.mac_ver()
print(platform.python_version_tuple())
if mac_ver is not None and mac_ver != "":
print("macOS version", mac_ver)
print(platform.platform())
print("Python", platform.python_build(), platform.python_compiler())
print("Executing in", "64bit" if sys.maxsize > 2 ** 32 else "32bit")
m = 4
n = 25_000_000
print('\nchunks * elements = m * n = {:,} * {:,} = {:,}\n'.format(m, n,
m*n))
print('Time Pi%18.15f Error of calculation function' % math.pi)
for f in [leibniz, madhava, madhava_leibniz, madhava_leibniz_starmap]:
report(f, m, n)
main()
推荐答案
我使用 itertools.cycle
稍微改变了 madhava()
函数:
I slightly changed the madhava()
function by using itertools.cycle
:
def madhava(k, n): # Optimized for speed any way you like.
# you don't need to allocate the array in advance, so comment it out
# series = [0.0] * (n - k + 1)
first_divisor = 2 * k + 1
last_divisor_plus_1 = 2 * n + 2
if k & 1:
series = [what / divisor for what, divisor in zip(cycle([-1, 1]), range(first_divisor, last_divisor_plus_1, 2))]
else:
series = [what / divisor for what, divisor in zip(cycle([1, -1]), range(first_divisor, last_divisor_plus_1, 2))]
return series
我机器上的原始版本(AMD 2400G,Ubuntu 18.04):
Original version on my machine (AMD 2400G, Ubuntu 18.04):
('3', '6', '7')
Linux-5.0.20-050020-generic-x86_64-with-Ubuntu-18.04-bionic
Python ('default', 'Oct 22 2018 11:32:17') GCC 8.2.0
Executing in 64bit
Time Pi 3.141592653589793 Error of calculation function
m * n = 4 * 25 = 100
0.000 3.131592903558554 0.00999975003123943 madhava
0.000 3.131592903558554 0.00999975003123943 leibniz
m * n = 4 * 250 = 1,000
0.000 3.140592653839794 0.000999999749998981 madhava
0.000 3.140592653839794 0.000999999749998981 leibniz
m * n = 4 * 2,500 = 10,000
0.001 3.141492653590034 9.99999997586265e-05 madhava
0.002 3.141492653590034 9.99999997586265e-05 leibniz
m * n = 4 * 25,000 = 100,000
0.009 3.141582653589720 1.0000000073340232e-05 madhava
0.016 3.141582653589720 1.0000000073340232e-05 leibniz
m * n = 4 * 250,000 = 1,000,000
0.091 3.141591653589774 1.0000000187915248e-06 madhava
0.150 3.141591653589774 1.0000000187915248e-06 leibniz
m * n = 4 * 2,500,000 = 10,000,000
0.890 3.141592553589792 1.0000000161269895e-07 madhava
1.546 3.141592553589792 1.0000000161269895e-07 leibniz
m * n = 4 * 25,000,000 = 100,000,000
9.002 3.141592643589326 1.0000467121074053e-08 madhava
15.699 3.141592643589326 1.0000467121074053e-08 leibniz
使用itertools.cycle
的版本:
('3', '6', '7')
Linux-5.0.20-050020-generic-x86_64-with-Ubuntu-18.04-bionic
Python ('default', 'Oct 22 2018 11:32:17') GCC 8.2.0
Executing in 64bit
Time Pi 3.141592653589793 Error of calculation function
m * n = 4 * 25 = 100
0.000 3.131592903558554 0.00999975003123943 madhava
0.000 3.131592903558554 0.00999975003123943 leibniz
m * n = 4 * 250 = 1,000
0.000 3.140592653839794 0.000999999749998981 madhava
0.000 3.140592653839794 0.000999999749998981 leibniz
m * n = 4 * 2,500 = 10,000
0.001 3.141492653590034 9.99999997586265e-05 madhava
0.002 3.141492653590034 9.99999997586265e-05 leibniz
m * n = 4 * 25,000 = 100,000
0.007 3.141582653589720 1.0000000073340232e-05 madhava
0.016 3.141582653589720 1.0000000073340232e-05 leibniz
m * n = 4 * 250,000 = 1,000,000
0.061 3.141591653589774 1.0000000187915248e-06 madhava
0.152 3.141591653589774 1.0000000187915248e-06 leibniz
m * n = 4 * 2,500,000 = 10,000,000
0.608 3.141592553589792 1.0000000161269895e-07 madhava
1.530 3.141592553589792 1.0000000161269895e-07 leibniz
m * n = 4 * 25,000,000 = 100,000,000
6.167 3.141592643589326 1.0000467121074053e-08 madhava
15.617 3.141592643589326 1.0000467121074053e-08 leibniz
另一个版本,使用itertools.starmap
和operator.truediv
:
Another version, using itertools.starmap
and operator.truediv
:
def madhava_leibniz_starmap(k, n):
return starmap(truediv, zip(cycle([1, -1] if k & 1 else [1, -1]), range(2*k+1, 2*n+2, 2)))
在我的电脑上这会产生:
On my computer this yields:
('3', '6', '7')
Linux-5.0.20-050020-generic-x86_64-with-Ubuntu-18.04-bionic
Python ('default', 'Oct 22 2018 11:32:17') GCC 8.2.0
Executing in 64bit
chunks * elements = m * n = 4 * 25,000,000 = 100,000,000
Time Pi 3.141592653589793 Error of calculation function
15.569 3.141592643589326 1.0000467121074053e-08 leibniz
8.968 3.141592643589326 1.0000467121074053e-08 madhava
6.182 3.141592643589326 1.0000467121074053e-08 madhava_leibniz
5.238 3.141592643589326 1.0000467121074053e-08 madhava_leibniz_starmap
这比列表理解快大约一秒.
Which is roughly one second faster than list comprehension.
这篇关于使用 Python 尽快从 Madhava–Leibniz 系列中获得子序列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!