Let there be an array of numbers [1, 2, 3, 4, 6, 3, 4, 0, 2] .

It is necessary to find a sequence of three (for example) numbers, the sum of which will be maximum .

Interested in an algorithmically efficient way without iteration , if there is one, because you need to use it on very large arrays . Thank.

  • For every three numbers, store the sum of the second and third and use, when the summation region is shifted, as a ready-made term? Winning 25% at once - Vladimir Martyanov

5 answers 5

Only for the purposes of performance comparison, at the request of @MaxU , otherwise their answer is quite working ), the straight-line version of Cython is an order of magnitude faster than s.rolling(3, min_periods=1).sum().idxmax() solutions:

 $ python -mtimeit -s 'import numpy as np; a = np.random.randint(10**4, size=10**6); from max_rolling_sum import max_rolling_sum as f' 'f(a, 3)' 100 loops, best of 3: 2.7 msec per loop $ python -mtimeit -s 'import numpy as np; a = np.random.randint(10**4, size=10**6); from max_rolling_maxu import max_rolling_sum as f' 'f(a, 3)' 10 loops, best of 3: 48.1 msec per loop

where max_rolling_sum.pyx :

 #cython: boundscheck=False ctypedef long array_type cpdef Py_ssize_t max_rolling_sum(array_type[:] arr, Py_ssize_t k) nogil: """arr[i:i+k].sum() is maximum.""" cdef Py_ssize_t N = arr.shape[0] if N < 1: return -1 # error: no sum cdef Py_ssize_t i cdef array_type sum_ = 0 for i in range(min(k, N)): # find first sum arr[:k].sum() sum_ += arr[i] cdef Py_ssize_t max_start = 0 cdef array_type max_sum = sum_ for i in range(k, N): # compute rolling sum arr[i-k+1:i+1].sum() sum_ -= arr[i - k] # pop (left) from old sum sum_ += arr[i] # append (right) to new sum if max_sum < sum_: max_sum = sum_ max_start = i - k + 1 return max_start

and max_rolling_maxu.py :

 import pandas as pd def max_rolling_sum(arr, k): """arr[i:i+k].sum() is maximum.""" s = pd.Series(arr) idx = s.rolling(k, min_periods=1).sum().idxmax() return max(idx - 2, 0)
  • Great! Thank you! - MaxU

It is possible for O (n) time and O (1) memory during a loop that will store the current maximum and at each iteration it will be necessary to calculate the sum of the current subsequence and compare it with the stored one. When using the "sliding window" O (n) memory is wasted.

  • It would be interesting and useful for others to look at the implementation and compare the speed of work ... ;-) - MaxU
  • @MaxU: added comparison on your request - jfs

Pandas Example:

Source Series:

 import pandas as pd In [109]: s = pd.Series([1,2,3,4,6,3,4,0,2]) In [110]: s Out[110]: 0 1 1 2 2 3 3 4 4 6 5 3 6 4 7 0 8 2 dtype: int64

Use the sliding window ( Series.rolling () ):

 In [111]: s.rolling(3, min_periods=1).sum() Out[111]: 0 1.0 1 3.0 2 6.0 3 9.0 4 13.0 5 13.0 6 13.0 7 7.0 8 6.0 dtype: float64 In [112]: idx = s.rolling(3, min_periods=1).sum().idxmax() In [113]: idx Out[113]: 4 In [114]: s.loc[idx-2:idx] Out[114]: 2 3 3 4 4 6 dtype: int64

Measuring speed for an array of 1.000.000 items:

 In [18]: a = np.random.randint(10**4, size=10**6) In [19]: a Out[19]: array([9918, 4299, 7829, ..., 7513, 3367, 7140]) In [20]: pd.options.display.max_rows = 15 In [21]: s = pd.Series(a) In [22]: %%timeit ...: idx = s.rolling(3, min_periods=1).sum().idxmax() ...: s.loc[idx-2:idx] ...: 115 ms ± 7.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) In [23]: s.shape Out[23]: (1000000,)

    Just take the maximum items. You can sort - O (n log n), but you can build a binary heap and extract several maxima - O (n + k log n).

      The answer @jfs actually shows a general approach to obtaining a convolution with a sequence of units: subtract the extreme number, add a new one. That is, it just provides the algorithm that you need, while in the answer chosen by the best, this algorithm is hidden in the module used (if this one is at all).

      You can try to optimize, but this is a complex optimization. In fact, a sequence of units is a characteristic of a low-pass filter, and this imposes restrictions on the derivatives of the result. That is, if at this step we received a conditionally “small” amount, even though we already have a conventionally “large” maximum, we can guarantee that we will not get a certain amount of iterations of the new maximum, and skip these iterations. Only in this case it is necessary to somehow recalculate the amount currently available. If this is done with the same algorithm, then optimization only eliminates the need to compare the value with the maximum at this step, that is, it does little. Although, it depends on the nature of the source array. If you have very large ones and a practical task, then probably these are not random numbers. You can try to get data on the characteristics of the sequence of a run ahead with some steps instead of 1. But these are complex optimizations, the way from the @jfs response itself is very fast and requires only 2 calls to each element of the array.