Python中的高效求和

我試圖在 Python 中有效地計算求和的總和：

WolframAlpha能夠計算出過高的 n 值：sum of sum。

我有兩種方法：for回圈方法和 np.sum 方法。我認為 np.sum 方法會更快。然而，它們是相同的，直到一個大的 n，之后 np.sum 有溢位錯誤并給出錯誤的結果。

我試圖找到計算這個總和的最快方法。

import numpy as np
import time

def summation(start,end,func):
    sum=0
    for i in range(start,end 1):
        sum =func(i)
    return sum

def x(y):
    return y

def x2(y):
    return y**2

def mysum(y):
    return x2(y)*summation(0, y, x)

n=100

# method #1
start=time.time()
summation(0,n,mysum)
print('Slow method:',time.time()-start)

# method #2
start=time.time()
w=np.arange(0,n 1)
(w**2*np.cumsum(w)).sum()
print('Fast method:',time.time()-start)

uj5u.com熱心網友回復：

這是一個非常快速的方法：

result = ((((12 * n   45) * n   50) * n   15) * n - 2) * n // 120

我是如何到達那里的：

1. 將內和重寫為眾所周知的x*(x 1)//2。所以整個事情就變成了sum(x**2 * x*(x 1)//2 for x in range(n 1))。
2. 重寫為sum(x**4 x**3 for x in range(n 1)) // 2.
3. 查找公式為sum(x**4)和sum(x**3)。
4. 將由此產生的混亂簡化為(12*n**5 45*n**4 50*n**3 15*n**2 - 2*n) // 120.
5. 霍納它。

如果在步驟 1. 和 2. 之后您知道它是 5 次多項式，則推匯出它的另一種方法：

3. 用一個簡單的實作計算六個值。
4. 從六個未知數（多項式系數）的六個方程計算多項式。我的做法與此類似，但與此相比，我的矩陣A是左右鏡像的，我將其稱為 y-vector b。

代碼：

from fractions import Fraction
import math
from functools import reduce

def naive(n):
    return sum(x**2 * sum(range(x 1)) for x in range(n 1))

def lcm(ints):
    return reduce(lambda r, i: r * i // math.gcd(r, i), ints)

def polynomial(xys):
    xs, ys = zip(*xys)
    n = len(xs)
    A = [[Fraction(x**i) for i in range(n)] for x in xs]
    b = list(ys)
    for _ in range(2):
        for i0 in range(n):
            for i in range(i0   1, n):
                f = A[i][i0] / A[i0][i0]
                for j in range(i0, n):
                    A[i][j] -= f * A[i0][j]
                b[i] -= f * b[i0]
        A = [row[::-1] for row in A[::-1]]
        b.reverse()
    coeffs = [b[i] / A[i][i] for i in range(n)]
    denominator = lcm(c.denominator for c in coeffs)
    coeffs = [int(c * denominator) for c in coeffs]
    horner = str(coeffs[-1])
    for c in coeffs[-2::-1]:
        horner  = ' * n'
        if c:
            horner = f"({horner} {' ' if c > 0 else '-'} {abs(c)})"
    return f'{horner} // {denominator}'

print(polynomial((x, naive(x)) for x in range(6)))

輸出（在線嘗試！）：

((((12 * n   45) * n   50) * n   15) * n - 2) * n // 120

uj5u.com熱心網友回復：

在快速 NumPy 方法中，您需要指定dtype=np.object以便 NumPy 不會將 Python 轉換int為它自己的 dtype（np.int64或其他）。它現在會給你正確的結果（檢查它高達 N=100000）。

# method #2
start=time.time()
w=np.arange(0, n 1, dtype=np.object)
result2 = (w**2*np.cumsum(w)).sum()
print('Fast method:', time.time()-start)

您的快速解決方案比慢速解決方案快得多。是的，對于較大的 N，但在 N=100 時，它已經快了 8 倍：

start=time.time()
for i in range(100):
    result1 = summation(0, n, mysum)
print('Slow method:', time.time()-start)

# method #2
start=time.time()
for i in range(100):
    w=np.arange(0, n 1, dtype=np.object)
    result2 = (w**2*np.cumsum(w)).sum()
print('Fast method:', time.time()-start)

Slow method: 0.06906533241271973
Fast method: 0.008007287979125977

編輯：更快的方法（由KellyBundy，南瓜）是使用純python。事實證明 NumPy 在這里沒有優勢，因為它沒有用于np.objects.

# method #3
import itertools
start=time.time()
for i in range(100):
    result3 = sum(x*x * ysum for x, ysum in enumerate(itertools.accumulate(range(n 1))))
print('Faster, pure python:', (time.time()-start))

Faster, pure python: 0.0009944438934326172

標籤：Python 表现 和 累积总和

上一篇：MongoDB：過濾和合并具有公共欄位的檔案

下一篇：應該在最小二乘法之前計算QR分解以加快程序嗎？