性能的各種numpy花式索引方法，也與numba

Question

由於我的程序快速索引Numpy陣列是非常必要的，花式索引考慮到性能沒有良好的聲譽，我決定做一些測試。特別是因爲Numba發展得相當快，我嘗試了哪些方法適用於numba。

正如我一直在使用下面的陣列爲我輸入的小型陣列測試：

import numpy as np 
import numba as nb 

x = np.arange(0, 100, dtype=np.float64) # array to be indexed 
idx = np.array((0, 4, 55, -1), dtype=np.int32) # fancy indexing array 
bool_mask = np.zeros(x.shape, dtype=np.bool) # boolean indexing mask 
bool_mask[idx] = True # set same elements as in idx True 
y = np.zeros(idx.shape, dtype=np.float64) # output array 
y_bool = np.zeros(bool_mask[bool_mask == True].shape, dtype=np.float64) #bool output array (only for convenience) 

而且我的大陣列測試以下陣列（這裏以應對從重複數據刪除的數字需要y_boolrandint）：

x = np.arange(0, 1000000, dtype=np.float64) 
idx = np.random.randint(0, 1000000, size=int(1000000/50)) 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 
y = np.zeros(idx.shape, dtype=np.float64) 
y_bool = np.zeros(bool_mask[bool_mask == True].shape, dtype=np.float64) 

這將產生以下的定時，而無需使用numba：

%timeit x[idx] 
#1.08 µs ± 21 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
#large arrays: 129 µs ± 3.45 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x[bool_mask] 
#482 ns ± 18.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
#large arrays: 621 µs ± 15.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.take(x, idx) 
#2.27 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 112 µs ± 5.76 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit np.take(x, idx, out=y) 
#2.65 µs ± 134 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 134 µs ± 4.47 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x.take(idx) 
#919 ns ± 21.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 108 µs ± 1.71 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x.take(idx, out=y) 
#1.79 µs ± 40.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# larg arrays: 131 µs ± 2.92 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit np.compress(bool_mask, x) 
#1.93 µs ± 95.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 618 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.compress(bool_mask, x, out=y_bool) 
#2.58 µs ± 167 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 637 µs ± 9.88 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit x.compress(bool_mask) 
#900 ns ± 82.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 628 µs ± 17.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit x.compress(bool_mask, out=y_bool) 
#1.78 µs ± 59.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 628 µs ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.extract(bool_mask, x) 
#5.29 µs ± 194 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 641 µs ± 13 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

並與numba，在nopython - 模式，cach ING和nogil使用jitting我飾索引的方式，這是由numba支持：

@nb.jit(nopython=True, cache=True, nogil=True) 
def fancy(x, idx): 
    x[idx] 

@nb.jit(nopython=True, cache=True, nogil=True) 
def fancy_bool(x, bool_mask): 
    x[bool_mask] 

@nb.jit(nopython=True, cache=True, nogil=True) 
def taker(x, idx): 
    np.take(x, idx) 

@nb.jit(nopython=True, cache=True, nogil=True) 
def ndtaker(x, idx): 
    x.take(idx) 

我們得到以下結果爲小型和大型陣列：

%timeit fancy(x, idx) 
#686 ns ± 25.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 84.7 µs ± 1.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit fancy_bool(x, bool_mask) 
#845 ns ± 31 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 843 µs ± 14.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit taker(x, idx) 
#814 ns ± 21.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 87 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit ndtaker(x, idx) 
#831 ns ± 24.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 85.4 µs ± 2.69 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

---

摘要

雖然沒有numba的numpy很明顯，小數組是迄今爲止最好的用布爾掩碼索引（大約是因子2與ndarray.take(idx)相比），對於較大的數組ndarray.take(idx)將表現最好，在這種情況下，大約比布爾索引快6倍。盈虧平衡點的陣列大小約爲1000單元，索引陣列大小約爲20單元。
對於具有1e5元素和5e3索引數組大小的數組，ndarray.take(idx)將大約是比布爾值掩碼索引更快。所以看起來布爾索引似乎會隨着數組大小而顯着減慢，但在達到某個數組大小閾值後會稍微增加。

對於numba jitted函數，除布爾掩碼索引外，所有索引函數都有一個小的加速。簡單的花式索引在這裏效果最好，但仍然比沒有jitting的布爾掩碼更慢。
對於較大的數組，布爾值掩碼索引比其他方法慢很多，甚至比非jitted版本要慢。其他三種方法都表現相當不錯，比非拼接版本快大約15％。

對於我的情況，有許多不同大小的數組，花式索引與numba是最好的方法。也許其他人也可以在這篇相當長的文章中找到一些有用的信息。

編輯：
對不起，我忘了問我的問題，我其實有。我剛剛在工作日結束時迅速輸入了這個數據，並完全忘記了它... 那麼，你知道比我測試的更好更快的方法嗎？使用Cython我的時間在Numba和Python之間。
由於索引數組只是預定義一次，並且在長時間迭代中沒有改變地使用，所以任何預先定義索引過程的方式都會很好。爲此我想到了使用步伐。但我無法預先定義一組自定義的步幅。是否有可能使用大步獲得預定義的視圖到內存中？

編輯2：
我想我會提出我的問題有關，將相同的值陣列上使用預定義的常量數組索引（其中僅值的變化，但它沒有形狀）幾百萬次的迭代一個新的更具體的問題。這個問題太籠統了，也許我也提出了一些有點誤導的問題。一旦我開啓新的問題，我會在這裏發佈鏈接！
Here is the link to the followup question.

Answer 1

你的總結不完全正確，你已經用不同大小的數組進行過測試，但是你沒有做的一件事就是改變索引元素的數量。

我它限於純索引和省略take（其有效地是整數數組索引）和compress和extract（因爲這些是有效布爾數組索引）。這些唯一的區別是不變的因素。方法take和compress的常數因子將小於numpy函數np.take和np.compress的開銷，但否則對於合理大小的陣列，效果將會忽略不計。

就讓我用不同的數字目前它：

# ~ every 500th element 
x = np.arange(0, 1000000, dtype=np.float64) 
idx = np.random.randint(0, 1000000, size=int(1000000/500)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 51.6 µs ± 2.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 
%timeit x[bool_mask] 
# 1.03 ms ± 37.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 


# ~ every 50th element 
idx = np.random.randint(0, 1000000, size=int(1000000/50)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 1.46 ms ± 55.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit x[bool_mask] 
# 2.69 ms ± 154 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 


# ~ every 5th element 
idx = np.random.randint(0, 1000000, size=int(1000000/5)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 14.9 ms ± 495 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
%timeit x[bool_mask] 
# 8.31 ms ± 181 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

所以這裏發生了什麼？很簡單：整數數組索引只需要訪問與索引數組中的值一樣多的元素。這意味着如果有很少的匹配，它會很快但很慢，如果有很多索引。但是，布爾數組索引總是需要遍歷整個布爾數組並檢查「true」值。這意味着它應該大致「不變」的陣列。

但是，別急，這不是布爾數組常量真的？爲什麼整數數組索引需要較長的時間（最後一種情況下），比布爾數組索引，即使它具有處理較少〜5倍的元素？

這就是它變得更加複雜的地方。在這種情況下，布爾數組在隨機的地方有True這意味着它會受到分支預測失敗。如果True和False將具有相同的出現次數，但是在隨機的地方，則這些將更有可能。這就是爲什麼布爾數組索引越來越慢 - 因爲True到False的比例得到了更多的平等，從而更加「隨機」。如果還有更多的時間，更多的True也會導致結果數組更大。

至於這個分支預測事情的例子用這個作爲例子（可以用不同的系統不同，/編譯）：

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[:1000000//2] = True # first half True, second half False 
%timeit x[bool_mask] 
# 5.92 ms ± 118 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[::2] = True # True and False alternating 
%timeit x[bool_mask] 
# 16.6 ms ± 361 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[::2] = True 
np.random.shuffle(bool_mask) # shuffled 
%timeit x[bool_mask] 
# 18.2 ms ± 325 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

所以True和False分佈將嚴重影響與布爾面具即使運行時它們包含相同數量的True s！對於compress函數也會看到同樣的效果。

對於整數數組索引（以及類似np.take），將會看到其他效果：緩存位置。在你的情況下，索引是隨機分佈的，所以你的計算機必須爲「處理器緩存」加載大量的「內存」，因爲兩個索引不太可能彼此靠近。

比較：

idx = np.random.randint(0, 1000000, size=int(1000000/5)) 
%timeit x[idx] 
# 15.6 ms ± 703 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

idx = np.random.randint(0, 1000000, size=int(1000000/5)) 
idx = np.sort(idx) # sort them 
%timeit x[idx] 
# 4.33 ms ± 366 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

通過排序指標的可能性極大增加，未來價值將已經在緩存中，這可能會導致巨大的速度提升。如果您知道索引將被排序（例如，如果它們是由排序的np.where創建的，這使np.where的結果對於索引特別有效），這是一個非常重要的因素。

所以，它不像整數數組索引對於小數組來說比較慢，而對於大數組來說比較快，這取決於更多的因素。兩者都有它們的用例，並且根據情況可能（相當）比另一個更快。

---

讓我來談一談關於numba的功能。首先一些一般性陳述：

• cache不會有什麼區別，它只是避免重新編譯函數。在交互式環境中，這實質上是無用的。如果你想將模塊封裝在模塊中，速度會更快。
• nogil本身不會提供任何速度提升。如果在不同的線程中調用它，速度會更快，因爲每個函數的執行都可以釋放GIL，然後多個調用可以並行運行。

，否則我不知道該怎麼numba用途不同實現這些功能，但是當你使用NumPy的在numba功能可能是慢或更快 - 但即使它的速度更快也不會快很多（可能除了小陣列）。因爲如果可以做得更快，NumPy的開發者也會實現它。我的經驗法則是：如果你能用NumPy做到這點（矢量化），不要打擾到Numba。只有當你無法使用矢量化的NumPy函數或者NumPy來使用太多的臨時數組時，numba纔會發光！