TLDR；我正在執行陣列操作（沒有數學運算），我發現 Cython 的速度要快得多。有沒有辦法在 NumPy 中加快速度；還是賽通？
語境
我正在撰寫一個函式，該函式旨在NxN從index兩個方向（其頂角沿對角線）向前取陣列的子集，并將其沿對角線向上移動一個位置。其次，我需要將頂行從index一個地方向左移動。最后，我需要在操作后將陣列中的最后一列設定為零。
該陣列是一個嚴格的上三角矩陣，這意味著從對角線向下的所有內容都設定為 0。這是我嘗試以一種優雅的方式存盤物件對之間的歷史碰撞資料（其索引由矩陣中的索引表示）。這類似于制作一個大小的嵌套串列，n!/(2(n-2)!)它表示長度索引串列的有序對n。在這個演算法中，我希望從碰撞配對矩陣中“移除”一個物件。
我在此實作中發現的優點是，與從嵌套串列中洗掉對并將索引成對移動到“要洗掉的索引”點之后相比，從矩陣中“洗掉沖突對”在計算上要少得多。
整個專案圍繞將 3D 模型自動“打包”成粉末床融合增材制造的構建體積。該演算法使用模擬退火，因此修剪碰撞集、存盤歷史資訊、添加/洗掉幾何的能力是最重要的，需要很好地優化。
例子
假設我們的陣列采用這種形式（不代表實際資料）。
arr =
[[0. 1. 2. 3. 4. 5. 6. 7. 8. 9.]
[0. 0. 2. 3. 4. 5. 6. 7. 8. 9.]
[0. 0. 0. 3. 4. 5. 6. 7. 8. 9.]
[0. 0. 0. 0. 4. 5. 6. 7. 8. 9.]
[0. 0. 0. 0. 0. 5. 6. 7. 8. 9.]
[0. 0. 0. 0. 0. 0. 6. 7. 8. 9.]
[0. 0. 0. 0. 0. 0. 0. 7. 8. 9.]
[0. 0. 0. 0. 0. 0. 0. 0. 8. 9.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 9.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
然后使用index = 3我們應該獲取子集中的所有內容index 1:n, index 1:n并將其設定為等于index:n-1, index:n-1。然后將頂行向左移動；再往后index。然后將最后一列設定為 0。
fun(3, arr)
[[0. 1. 2. 4. 5. 6. 7. 8. 9. 0.]
[0. 0. 2. 3. 4. 5. 6. 7. 8. 0.]
[0. 0. 0. 3. 4. 5. 6. 7. 8. 0.]
[0. 0. 0. 0. 5. 6. 7. 8. 9. 0.]
[0. 0. 0. 0. 0. 6. 7. 8. 9. 0.]
[0. 0. 0. 0. 0. 0. 7. 8. 9. 0.]
[0. 0. 0. 0. 0. 0. 0. 8. 9. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 9. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
實作一：純NumPy
再次假設arr是一個NxN矩陣。
def fun(index, n, arr):
arr[index:-1, index:-1] = arr[index 1:, index 1:]
arr[0, index:-1] = arr[0, index 1:]
arr[:, n-1:] = 0
return arr
實作 2：Cython
請耐心等待，因為這是我第一次實施 Cython。
@cython.boundscheck(False)
def remove_from_collision_array(int index, int n, double[:,:] arr):
cdef int i, j, x_shape, y_shape
x_shape = arr.shape[0]
for i in range(index, x_shape):
for j in range(index, x_shape):
if j <= i:
# We are below the diagonal, do nothing
continue
elif i >= n-1 or j >= n-1:
arr[i, j] = 0
else:
arr[i, j] = arr[i 1, j 1]
arr[0, index:-1] = arr[0, index 1:]
arr[:, n-1:] = 0
return np.asarray(arr)
討論
Before anybody gets upset, yes I don't know what I'm doing in Cython. I disabled bounds_checking because it really really speeds things up. And I'm performing a bounds check in the loop with one of my elif statements.
I initially thought there would be no way that performing this operation in a loop would be faster than NumPy. I pre-allocate a NumPy array of size 5000x5000 to avoid needing to append, etc on the fly. I even tested the Cython implementation using the same 3 lines as the Numpy one, but it also performs poorly.
You can see that using index=0 will require the most computation. So I use that as a benchmark. While testing this in a loop, I've found that the Cython implementation is about 50% faster than the Numpy version. Perhaps this is because I am not adequately using the tools NumPy has to offer?
I am by no means a computer scientist, nor do I know if this is the best route. I'm a designer prototyping a system. If anybody has any insight on how to make this scream even faster, please let me know!
Update on the answer
Thanks to Jerome for teaching me something today! This will be instrumental in making this package run at lightning speed. I've added his insights to my code, resulting in a massive performance boost for two reasons that I can see:
- I've cut the number of loop iterations by
n*(n-1)/2by starting thej-loop above the diagonal. - I've removed all conditional statements.
Here is the updated Cython:
@cython.boundscheck(False)
@cython.wraparound(False)
def remove_from_collision_arrayV2(int index, int n, double[:,:] arr):
cdef int i, j
# Shift the diagonal matrix
for i in range(index, n-1):
for j in range(i, n-1):
arr[i, j] = arr[i 1, j 1]
# Shift the rop row
for j in range(index, n-1):
arr[0, j] = arr[0, j 1]
# Set Column column n-1 to zero
for i in range(n):
arr[i, n-1] = 0
return np.asarray(arr)
For benchmarking purposes. Performing this iteration 500 times using index=0 on a 500x500 matrix:
Original NumPy Code: 52.8s
Original Cython Code: 16.47s - 3.2x Speedup
Updated Cython Code: 0.014s - 3550x Speedup
uj5u.com熱心網友回復：
arr[index:-1, index:-1] = arr[index 1:, index 1:]Numpy 和 Cython 中的運算式都很慢并且 Cython 代碼更快的原因有點違反直覺：這個運算式在 Numpy 和 Cython 中都沒有有效實作。
實際上，Numpy 將右側 ( arr[index 1:, index 1:])復制到即時分配的臨時陣列中。然后將臨時陣列復制到左側 ( arr[index:-1, index:-1])。這意味著進行了兩次記憶體復制，而只能使用一次。更糟糕的是：復制的記憶體非常大，無法放入快取中，從而導致更大的開銷（在某些處理器上，例如主流的 x86/x86-64 處理器，回寫策略會導致額外的慢速讀取）。而且，新的臨時陣列會導致許多頁面錯誤，從而減慢復制速度。
Numpy 這樣做是因為左側和右側可能會重疊（這里就是這種情況），因此復制記憶體位元組的順序很重要。Numpy 使用緩慢的保守方法而不是優化的實作。這是一個錯過的優化。Cython 做同樣的事情。
您的 Cython 代碼不會受到所有這些開銷的影響：它相對有效地直接就地復制陣列。讀取的值保存在快取中，然后立即寫入，這樣回寫策略就不是問題。此外，沒有臨時陣列或頁面錯誤。最后，與前面提到的運算式相比，您的Cython 代碼不會復制三角矩陣的下半部分，從而導致要復制的位元組更少。
減少 Numpy 運算式開銷的一種方法是逐塊復制矩陣并為此分配一個小的臨時緩沖區（通常是矩陣的幾行）。然而，這遠非易事，因為 CPython 回圈通常非常慢，并且塊大小應該適合快取，因此該方法可能很有用......
進一步優化：條件很慢。您可以通過j在 處開始-based 回圈并在 處i 1結束來洗掉它們n-1。j然后另一個基于回圈可以填充大于 的值n-1。出于同樣的原因，i-based 回圈應該以 at 結束，n-1然后另一個回圈可以填充陣列的剩余部分。一個好的編譯器應該使用更快的SIMD 指令。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/365833.html
下一篇：使用另一個陣列將陣列轉換為1和0