总和超过阈值的最小间隔

Question

在非负1D数组 x 中，我们希望找到最短的切片，以便 x [start：end] end] .sum（）＆gt;阈值，带有可选约束， start＆lt; = argmax（x）＆lt;结束。必须与浮子和整数一起工作。

是否有已知的算法可以实现这一目标？我已经实施了一个在这里，但它不如我希望，理想情况下应该没有重量级依赖性（例如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中可以接受。 ， for 等 - 除非某人可以指向轻量级的numba ...

Answer 1

这让我想起了找到包括集合的所有成员的最小窗口的问题，该窗口可以在O（n）时间和O（k）空间中使用两个指针来解决。在我们的情况下，o（1）空间似乎足够了，因为我们只对一笔款项感兴趣。

移动正确的指针，直到达到总和为止。移动左指针，直到总和再次太低为止。然后移动正确的指针等。解决读者留给读者的gragmax约束。

Answer 2

只是我的几美分：

1. ，因为数组是非负的，所以每个索引中包含运行总和的列表已经是一个排序的列表。

2. 在每个索引上计算运行总和，并构建一个元组列表（runned_sum，current_index）。

3. 如果索引的运行总和超过了阈值的外观，则在运行总和列表中的最大值（runned_sum -sum -threshold）的最大值外观，使用二进制搜索在当前索引处不包括一个在当前索引处的值

4. 现在，当前范围是[index_found_found_by_binary_binary_search_search +1，curr_index]

5. 在所有此类范围内最小化。

在您的示例中：
运行总和为： [0，1，3，6，10，19，26，27，27，27，27，27]

总和（26）超过索引的阈值

22.99在阈值和总和之间为26-22.99 = 3.01。

查找小于 3.01的最大值 - 这可以通过二进制搜索来完成。
我们需要最大的价值，因为我们想最大程度地减少范围。

小于3.01的

3

最大的值是 范围。

不确定这是否是您已经做的。

Answer 3

感谢 @גלעדגלעד的指示。 numba/plain Python是在这里 >），具有贪婪的验证，以及下面的Cython（ numpy tutorial ）代码> float64 ，对于 float32 的速度更快10％当 len（x）= 1E6 时。它们比我可能想出的最快的numpy vectorized Impem快X10。

注意，对于 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 约束可以通过边界来满足约束左和右适当地，当然，一旦知道正确的间隔，我们就可以轻松获取确切的索引。与Numba不同，Cython的轻量级保留了Python的语法减去键入（至少对于我的情况）。