Smallest interval whose sum exceeds a threshold

user_10133797 0
Viewed 129

In a non-negative 1D array x, we wish to find the shortest slice such that x[start:end].sum() > threshold, with the optional constraint that start <= argmax(x) < end. Must work with floats and integers.

Is there a known algorithm to accomplish this? I have implemented one here, but it's not as fast as I wish, and ideally there shouldn't be a heavyweight dependency (e.g. numba). Example:

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]

@גלעד ברקן's answer is acceptably fast in numba; my implem. Though, non-numba is strongly preferred, meaning minimizing if, for, etc - unless someone can point to a lightweight numba...

numpy search algorithm python performance
3 Answers

This reminds me of the problem of finding the smallest window that includes all members of a set, which can be solved in O(n) time and O(k) space with two pointers. In our case, O(1) space would seem to be enough since we're only interested in a sum.

Move the right pointer until the sum is achieved. Move the left pointer just until the sum is again too low. Then move the right pointer, etc. Addressing the argmax constraint left to the reader.

user_20347870

Just my few cents:

  1. Because the array is non-negative the list containing running sum at each index is already a sorted list.

  2. Compute running sum at each index and construct a list of tuples (running_sum, current_index).

  3. If the running sum at an index exceeds the threshold look for the greatest value that is less than (running_sum - threshold) in the list of running sums excluding the one at current index using binary search

  4. Now the current range is the [index_found_by_binary_search+1, curr_index]

  5. Minimize upon all such ranges.

In your example: the running sum is: [0, 1, 3, 6, 10, 19, 26, 27, 27, 27, 27]

The sum(26) exceeds threshold of 22.99 at index = 6

Now difference between threshold and sum is 26 - 22.99 = 3.01.

Look for the greatest value that is smaller than 3.01 - this can be done by binary search. We need greatest value because we want to minimize the range.

The greatest value is 3 that is smaller than 3.01 and can be found at index 2.

The result is the range [2+1, 6] = [3,6]

Now do this all along the array and minimize upon the length of the range.

Not sure if that is what you already did.

user_14103030

Thanks to @גלעד ברקן for the pointers. Numba/plain Python is here (just add @jit), with greedy validation, and below's Cython (numpy tutorial), which equals Numba's speed on float64 and is 10% faster for float32 when len(x)=1e6. They're x10 faster than the fastest numpy-vectorized implem I could come up with.

Note, for float32 and long sequences, it suffers from roundoff imprecision, and instead one should compute the sum as (though it's slower):

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

The argmax constraint is easily satisfied by bounding left and right appropriately, and of course we can fetch the exact indices easily once we know the right interval. Unlike Numba, Cython's lightweight while retaining Python's syntax minus typing (at least for my case).

user_101337970
Related