在非負一維陣列x中，我們希望找到最短的切片 滿足x[start:end].sum() > threshold，并具有可選的約束條件start <= argmax(x) < end。必須使用浮點數和整數。
有沒有已知的演算法來完成這個？我在這里實作了一個，但它沒有我希望的那么快，理想情況下不應該存在重量級依賴（例如 numba）。例子：
x = [0, 1, 2, 3, 4, 9, 7, 1, 0, 0, 0]
threshold = 3 4 9 7 - .01
start, end = func(x, threshold)
print(x[start:end])
[3 4 9 7]
@???? ???? 的答案在 numba 中是可以接受的；我的實作。雖然，非 numba 是強烈首選，這意味著最小化if,for等 - 除非有人可以指向一個輕量級的 numba ...
uj5u.com熱心網友回復：
只是我的幾分錢：
因為陣列是非負的，所以在每個索引處包含運行總和的串列已經是一個排序串列。
計算每個索引處的運行總和并構造一個元組串列（running_sum，current_index）。
如果索引處的運行總和超過閾值，則使用二進制搜索在運行總和串列中查找小于 (running_sum - threshold) 的最大值，不包括當前索引處的值
現在當前范圍是 [index_found_by_binary_search 1, curr_index]
最小化所有這些范圍。
在您的示例中：運行總和為：[0, 1, 3, 6, 10, 19, 26, 27, 27, 27, 27]
sum(26) 在索引 = 6 處超過閾值 22.99
現在閾值和總和之間的差是 26 - 22.99 = 3.01。
尋找小于3.01 的最大值——這可以通過二分搜索來完成。我們需要最大的價值，因為我們想最小化范圍。
最大值是小于 3.01 的 3，可以在索引 2 處找到。
結果是范圍 [2 1, 6] = [3,6]
現在沿著陣列執行此操作并最小化范圍的長度。
不確定這是否是你已經做過的。
uj5u.com熱心網友回復：
這讓我想起了尋找包含集合所有成員的最小視窗的問題，可以用兩個指標在 O(n) 時間和 O(k) 空間內解決。在我們的例子中，O(1) 空間似乎就足夠了，因為我們只對總和感興趣。
向右移動指標，直到求和。移動左指標直到總和再次太低。然后移動右指標等。將 argmax 約束留給讀者。
uj5u.com熱心網友回復：
感謝@???? ???? 的指點。Numba/plain Python 在這里（只需添加@jit），帶有貪婪驗證，下面是 Cython（numpy 教程），它等于 Numba 的速度，并且在when 時float64快 10% 。它們比我能想到的最快的 numpy-vectorized 實作快 10 倍。float32len(x)=1e6
請注意，對于float32長序列，它會受到舍入不精確的影響，而應該將總和計算為（盡管它更慢）：
cs = np.hstack([0., np.cumsum(x)])
sm = cs[end] - cs[start]
import cython
float_int = cython.fused_type(cython.floating, cython.integral)
@cython.wraparound(False)
cpdef int smallest_interval_over_threshold(float_int[:] x, float_int threshold):
cdef Py_ssize_t N = x.shape[0]
cdef float_int[:] x_view = x
cdef Py_ssize_t left = 0
cdef Py_ssize_t right = 1
cdef Py_ssize_t min_size = N
cdef float_int sm = x_view[left]
while right < N:
if sm > threshold:
min_size = min(min_size, right - left)
sm -= x_view[left]
left = 1
else:
sm = x_view[right]
right = 1
while left < N and sm > threshold:
min_size = min(min_size, right - left)
sm -= x[left]
left = 1
cdef int min_size_int = <int>min_size
return min_size_int
約束很容易通過argmax有界left和right適當地滿足，當然，一旦我們知道正確的間隔，我們就可以輕松地獲取確切的索引。與 Numba 不同，Cython 的輕量級同時保留了 Python 的語法減去型別（至少對我而言）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/497798.html