python - 使用 Python 尽可能快地从 Madhava–Leibniz 系列中获得子序列
问题描述
Madhava–Leibniz 系列: 我所需要的只是创建一个从元素 k 到元素 n 的子序列: 从这个系列中尽可能快 地创建和返回。
我从 'leibniz' 单线函数开始,一步一步地通过反复试验的方法工作到 'madhava' 函数,它快了两倍。
更新:感谢Andrej Kesely的建议和两个破纪录的功能:“madhava_leibniz”(比之前的记录提高 20%)和“madhava_leibniz_starmap”(另外 15%)。
现在最快的时间属于一个新的函数“madhava_leibniz”。这比第一个'leibniz'版本快2.8!
现在我的脚本的输出:
('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 以缩短测试时间
Pi 计算和精度仅用于测试创建的子序列。时间是最重要的。
我仍在学习 Python,可能错过了一些让它更快的方法。你能推荐一个比“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()
解决方案
我通过使用稍微改变了madhava()
功能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):
('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
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)))
在我的电脑上,这会产生:
('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
这比列表理解快大约一秒。
推荐阅读
- ios - 扩展可扩展表格查看单元格以进一步扩展
- javascript - Vue.js [v-cloak] 不使用 CSS 过渡
- c# - 具有隐藏可见性的 TextBlock 不保留空间
- python - 根据第二个数据帧设置数据帧的值
- django - Django admin:由信号引起的完整性错误
- javascript - jquery根据查询字符串删除标签
- z3 - 避免在 Z3 中截断大型模型
- python - 错误:表格簿有 4 列,但提供了 5 个值
- mvc.jquery.datatables - 如何在 jquery datatables ajax 中将下拉列表的值作为参数传递?
- c# - vsts 在 Linux 上发布 dotnet core