在 numpy 庫中，可以將一個串列傳遞給numpy.searchsorted函式，從而它一次在不同的串列中搜索一個元素，并回傳一個與保持順序所需的索引大小相同的陣列。但是，如果對兩個串列都進行了排序，這似乎是在浪費性能。例如：
m=[1,3,5,7,9]
n=[2,4,6,8,10]
numpy.searchsorted(m,n)
會回傳[1,2,3,4,5]正確的答案，但看起來這將具有復雜性 O(n ln(m))，如果一個人簡單地回圈通過 m，并有某種指向 n 的指標，那么復雜性似乎是更像 O(n m)？NumPy 中是否有某種功能可以做到這一點？
uj5u.com熱心網友回復：
您可以使用sortednp，不幸的是它沒有提供太多的靈活性，在下面的代碼片段中，我使用了它的合并跟蹤索引，但它產生了三個陣列，使用的記憶體是必要的四倍，但它比 searchsorted 快。
import numpy as np
import sortednp as snp
a = np.cumsum(np.random.rand(1000000))
b = np.cumsum(np.random.rand(1000000))
def snp_search(a,b):
m, (ib, ia) = snp.merge(b, a, indices=True)
return ib - np.arange(len(ib))
assert(np.all(snp_search(a,b) == np.searchsorted(a,b)))
np.searchsorted(a, b); #58 ms
snp_search(a,b); # 22ms
uj5u.com熱心網友回復：
AFAIK，這不可能在線性時間內僅使用 Numpy 而不對輸入進行額外假設（例如，整數很小且有界）。另一種解決方案是使用 Numba 手動進行合并：
import numba as nb
# Note: Numba requires a function signature with well defined array types
@nb.njit('int64[:](int64[::1], int64[::1])')
def search_both_sorted(a, b):
i, j = 0, 0
result = np.empty(b.size, np.int64)
while i < a.size and j < a.size:
if a[i] < b[j]:
i = 1
else:
result[j] = i
j = 1
for k in range(j, b.size):
result[k] = i
return result
a, b = np.cumsum(np.random.randint(0, 100, (2, 1000000)).astype(np.int64), axis=1)
result = search_both_sorted(a, b)
更快的實作包括使用無分支方法，以便在大小相同時消除分支錯誤預測的開銷（尤其是在隨機/不可預測的輸入上）。此外，如@MichaelSzczesny 所指出的，該演算法在較小時可以更快，因此在這種情況下使用非常有效。請注意，Numba 的實作可能比 Numpy 的慢一點，因此最好選擇 Numpy 實作。這是優化版本：abO(n log m)bnp.searchsortednp.searchsorted
@nb.njit('int64[:](int64[::1], int64[::1])')
def search_both_sorted_opt_numba(a, b):
sa, sb = a.size, b.size
# Choose the best algorithm
if sb < sa * 0.15:
# Use a version with branches because `a[i] < b[j]`
# should be most of the time true.
i, j = 0, 0
result = np.empty(b.size, np.int64)
while i < a.size and j < b.size:
if a[i] < b[j]:
i = 1
else:
result[j] = i
j = 1
for k in range(j, b.size):
result[k] = i
else:
# Use a branchless approach to avoid miss-predictions
i, j = 0, 0
result = np.empty(b.size, np.int64)
while i < a.size and j < b.size:
tmp = a[i] < b[j]
result[j] = i
i = tmp
j = ~tmp
for k in range(j, b.size):
result[k] = i
return result
def search_both_sorted_opt(a, b):
sa, sb = a.size, b.size
# Choose the best algorithm
if 2 * sb * np.log2(sa) < sa sb:
return np.searchsorted(a, b)
else:
return search_both_sorted_opt_numba(a, b)
searchsorted: 19.1 ms
snp_search: 11.8 ms
search_both_sorted: 6.5 ms
search_both_sorted_branchless: 4.3 ms
考慮到代碼已經高度優化，優化后的無分支 Numba 實作速度比后者快 4.4 倍左右。由于快取區域性，它可以在很大時甚至更快。searchsortedsearchsortedab
uj5u.com熱心網友回復：
np.searchsorted從源代碼中可以看出已經考慮到了這一點：
/*
* Updating only one of the indices based on the previous key
* gives the search a big boost when keys are sorted, but slightly
* slows down things for purely random ones.
*/
if (cmp(last_key_val, key_val)) {
max_idx = arr_len;
}
else {
min_idx = 0;
max_idx = (max_idx < arr_len) ? (max_idx 1) : arr_len;
}
這里min_idx, max_idx用于對陣列進行二分查找。如果last_key_val < key_valthen onlymax_idx重置為陣列長度，但min_idx仍保持其當前值，即二進制搜索從與前一個鍵相同的下邊界開始。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/436262.html
上一篇：如何比較前一行的值的百分比差異
下一篇：高效的陣列整形和平鋪操作