我想估計從陣列 x 中隨機抽取的資料點大于或等于從陣列 y 中隨機抽取的點的概率。我想通過比較所有可能的值對來做到這一點。
我認為一個幼稚的實作看起來像這樣：
def probability_x_gte_y(array_x, array_y):
gte_counter = 0
n_comparisons = len(array_x) * len(array_y)
for vx in array_x:
for vy in array_y:
if vx >= vy:
gte_counter = 1
return gte_counter / n_comparisons
但我相信有一種更有效的方法來計算這個，特別是考慮到 array_x 和 array_y 中兩組點的分布很可能很好地分開（換句話說，兩個一維陣列之間的重疊是相對于涵蓋的點的總范圍來說可能很小。）
uj5u.com熱心網友回復：
一種更快的實作是對陣列中的一個進行排序，因此由于二分搜索，可以更快地找到大于給定值的數量。此實作在運行時運行，O(n log n)而原始運行在O(n * n).
def probability_x_gte_y_opt2(array_x, array_y):
n_comparisons = len(array_x) * len(array_y)
sorted_x = np.sort(array_x)
gte_counter = n_comparisons - np.searchsorted(sorted_x, array_y).sum()
return gte_counter / n_comparisons
在大小為 5000 的隨機陣列上，這在我的機器上大約快 3890 倍（2.69s 對 0.69ms）！
請注意，這可以撰寫一個O(n)及時運行的演算法：您可以對兩個陣列使用基數排序，然后在兩個排序陣列之間進行一種自定義計數合并。但是，Numpy 還沒有實作基數排序，并且不能用 Numpy 輕松實作快速計數合并。
uj5u.com熱心網友回復：
如果您的陣列足夠小，那么詳盡的計算是正確的。如果您的陣列太大，那么您可以執行一個模擬來收斂正確的概率，給您一個估計。
如果您無法精疲力竭并想要一個準確的答案，那么您需要將問題分解為更小的塊。例如，假設 X 和 Y 中的所有點都在區間 (0,1) 中。如果我們將該區間分解為十個子區間，(0,0.1),...(0.9,1); 然后我們可以窮盡每個子區間并計算條件概率。從理論上講，這甚至可以減少到僅包含單個點的間隔，但我假設在耗盡大小和條件概率樹大小之間會有一個權衡。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/393345.html
上一篇：使用影像處理檢測近水平線
下一篇：無法解開一個numpy陣列