我正在對“大”（80,000 個元素）numpy 陣列“x_a”進行大量處理
order = np.arange(1, 101)
rho = [spctr.aryule(x_a, i, norm='biased')[1] for i in order]
（numpy 匯入為 np，光譜匯入為 spctr），我正在對一個函式進行一系列獨立呼叫，該函式將陣列作為輸入（并且不修改它）并獲取不同 i 值的結果并存盤它們在 rho 串列中。
在這個例子中，它需要 2m 20s，但隨著階數上限的增加，它會迅速上升（1h 為 500），所以我試圖通過并行處理來加快速度。
按照一些指南，似乎多處理是最好的選擇，因為執行緒受到全域解釋器鎖的限制，所以我嘗試了這個：
order = np.arange(1, 101)
def f1(i):
return spctr.aryule(x_a, i, norm='biased')[1]
with mp.Pool() as pool:
rho = pool.map(f1, order)
（多處理匯入為 mp）這更糟糕，我在 10 分鐘后終止了該行程，似乎太多資料的酸洗太責備了，所以接下來我嘗試從 multiprocessing.Pool 匯入 ThreadPool 并這樣做：
order = np.arange(1, 101)
def f1(i):
return spctr.aryule(x_a, i, norm='biased')[1]
with ThreadPool() as pool:
rho = pool.map(f1, order)
然而，回到更合理的 2m 和 30s 的執行時間，這并沒有改善。
我對使用python進行并行處理的方式非常陌生……請幫忙。
uj5u.com熱心網友回復：
在這里使用多處理不是一個好主意。事實上，aryule是非常低效的。并行化低效的實作只會浪費更多資源。此外，aryule內部作業的方式會導致并行化速度不會快很多。我們實際上可以撰寫一個速度快得多的實作順序運行。
分析
在這個例子中，它需要 2m 20s，但隨著階數上限的增加，它會迅速上升（1h 為 500），所以我試圖通過并行處理來加快速度。
這是因為aryule計算在 中運行的相關性O(order * len(X))。訂單越大，執行越慢。測驗所有訂單會導致整個演算法至少O(order^2 * len(X))及時運行，這對于實際輸入來說是非常糟糕的。首先要做的是提高演算法的復雜度。這是可能的，因為使用的相關性aryule已經迭代了從 0 到的所有順序，order因此您的代碼只是一遍又一遍地重新計算相同的作業。不過，這并不是一件容易的事，因為它需要查看此處可用的包的來源并了解代碼在您的特定情況下會做什么。
由于相關性從 0 迭代到order并且您也這樣做，因此第一次迭代比最后一次迭代快得多。這會導致作業不平衡，這對并行化是有害的，因為時間由最慢的迭代控制。在最壞的情況下，執行速度可能比它可能的速度慢兩倍（由于只有一半的執行緒實際作業）。
要了解如何撰寫高效的代碼，我們首先需要了解它實際上是多么低效。相關性似乎是這里的主要瓶頸，因為在您的示例中花費了 >99% 的時間。這是一個等效的簡化實作：
import spectrum
import numpy as np
def correlation(x, order):
x = np.array(x)
N = len(x)
assert order < N, 'lag must be less than len(x)'
r = np.zeros(order, dtype=float)
for k in range(0, order 1):
nk = N - k - 1
sum = 0
for j in range(0, nk 1):
sum = sum x[j k] * x[j]
if k == 0:
r0 = sum / float(N)
else:
r[k-1] = sum / float(N)
r = np.insert(r, 0, r0)
return r
def aryule(X, order):
r = correlation(X, order)
A, P, k = spectrum.LEVINSON(r, allow_singularity=True)
return A, P, k
order = np.arange(1, 101)
rho = [spctr.aryule(x_a, i)[1] for i in order]
正如我們所見，主熱回圈correlation是用純 Python 撰寫的，并且沒有向量化！這在性能方面非常糟糕。np.array(x)在此處不需要時執行陣列的副本。某些運算式1 / float(N)無緣無故地重新計算了很多次。np.insert執行陣列的副本以添加一個專案，而這不是必需的：可以首先使用正確的大小直接創建陣列。
更快的實作（使用矢量化）
這是一個更快的實作：
def correlation(x, order):
assert order < x.size, 'lag must be less than len(x)'
invN = 1.0 / x.size
r = np.zeros(order 1, dtype=float)
r[0] = np.sum(x * x) * invN
for k in range(1, order 1):
r[k] = np.sum(x[k:] * x[0:x.size-k]) * invN
return r
def aryule(X, order):
r = correlation(X, order)
A, P, k = spectrum.LEVINSON(r, allow_singularity=True)
return A, P, k
order = np.arange(1, 101)
rho = [spctr.aryule(x_a, i)[1] for i in order]
代碼不僅快了幾個數量級，而且更簡單。我還希望代碼更加準確，因為參考和在數值上非常不穩定！
更好的演算法復雜度
此外，我們可以只計算一次相關性并計算LEVINSON子陣列上的操作，從而大大提高演算法的復雜性和執行時間。這是最終的實作：
# [...] Same code as above
def multiAryuleP(X, orders):
maxOrder = np.max(orders)
r = correlation(X, maxOrder)
rho = np.empty(orders.size)
for i in range(orders.size):
rho[i] = spectrum.LEVINSON(r[:orders[i] 1], allow_singularity=True)[1]
return rho
order = np.arange(1, 101)
rho = multiAryuleP(X, order)
O(order*len(X) order^3)請注意，由于 的復雜度為 ，LEVINSON因此運行整體演算法O(order^2)。
更快的實作（使用 Numba）
事實證明，實作的spectrum.LEVINSON效率也很低。話雖如此，使用 Numpy 有效地實作這一點并非易事。一種解決方案是使用 Numba，它是一種 JIT 編譯器，從具有純 Python 回圈的基于 Numpy 的代碼生成高效代碼。Cython 也可以很好地完成這項作業。這是一個例子：
import numba as nb
# [...] Same code as above
@nb.njit('(float64[::1],)', fastmath=True)
def levinsonP(r):
A = np.zeros(r.size - 1)
P = r[0]
if r.size > 1:
save = r[1]
temp = -save / P
P *= 1.0 - temp * temp
A[0] = temp
for k in range(1, r.size - 1):
save = r[k 1]
for j in range(0, k):
save = A[j] * r[k-j]
temp = -save / P
P *= 1.0 - temp * temp
A[k] = temp
khalf = (k 1) // 2
for j in range(0, khalf):
kj = k-j-1
save = A[j]
A[j] = save temp * A[kj]
if j != kj:
A[kj] = temp*save
return P
def multiAryuleP(X, orders):
maxOrder = np.max(orders)
r = correlation(X, maxOrder)
rho = np.empty(orders.size)
for i in range(orders.size):
rho[i] = levinsonP(r[:orders[i] 1])
return rho
order = np.arange(1, 101)
rho = multiAryuleP(X, order)
性能結果
這是我機器上的結果（使用 i5-9600KF 處理器）：
Initial implementation: 74000 ms
Vectorized implementation: 300 ms
Better complexity vectorization: 75 ms
Better complexity vectorization Numba: 4.5 ms
Optimal implementation: < 1.0 ms
最終實作快了大約16400 倍，而且仍然是順序的！更不用說更大的訂單甚至更快（500 的速度超過 40000 倍）。
可能的進一步改進
如果這還不夠，不是說復雜度multiAryuleP肯定可以提高。levinsonP實際上，可以避免重新計算 in 中的某些運算式，因此這部分可以O(order)快上幾倍。此外，當然可以使用 FFT 來顯著更快地計算相關性。或者，可以使用 Numba 并使用基于切片的方法進一步優化相關性，因此實作可以更加快取友好。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/533225.html
上一篇：減少函式的時間（Python）