I used sum() in a loop and it take more than 4s to execute, is the sum() equal to nested loop here?
def arrayMaxConsecutiveSum(inputArray, k):
cop=k
lis=[]
i=0
while i < len(inputArray):
inpu=sum(inputArray[i:cop])
lis.append(inpu)
cop+=1
i+=1
return max(lis)
sum is implemented as a C++ library, so it is still going to be faster than a Python for-loop, although you're still running nested loops either way. To illustrate, I timed your code here, as well as a modified code that uses a Python loop instead:
def arrayMaxConsecutiveSumLoop(inputArray, k):
cop=k
lis=[]
i=0
while i < len(inputArray) - k:
inpu = 0
for j in range(i, cop): # for-loop in place of sum
inpu += inputArray[j]
lis.append(inpu)
cop += 1
i += 1
return max(lis)
The timings were:
arrayMaxConsecutiveSum(np.random.rand(10000), 100)
111 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
arrayMaxConsecutiveSumLoop(np.random.rand(10000), 100)
198 ms ± 4.16 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
so the implementation with sum (your version) is faster by about a factor of two!
I rewrote your function using numpy to make it way faster! This implementation has no nested loops and is O(n), as well as being implemented with the very fast numpy libraries.
import numpy as np
def array_max_consecutive_sum(input_array, k):
result = np.cumsum(input_array)
return max(result[k:] - result[:-k])
array_max_consecutive_sum(np.random.rand(10000), 100)
688 µs ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
That's more than 150 times faster!
Incidentally, the accepted answer (as of this writing) gives timing:
6.46 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Fast, but still only a tenth as fast as the numpy implementation above. Also, the result is wrong.
dd = lambda x,y: max(sum(x[i:i+y])for i in range(len(x)-y+1)) and now time it
%timeit my_function_here(args) or a whole cell by putting %%timeit (two percent-signs) at the top. It will handle running multiple loops and calculating the timing for you.
Yes, in order to add all the elements together, sum code must traverse the inputArray (from i to cop).
Additionally, len(inputArray) must also traverse the entire array to get its length. Thus, your solution is O(n*k)
You can optimize your code to an O(n) solution with the following:
def arrayMaxConsecutiveSum(inputArray, k):
max = sum(inputArray[0:k])
bucket = max
count = len(inputArray)
for i in range(1, 1 + count - k):
prev = inputArray[i - 1]
cur = inputArray[i + k - 1]
bucket += cur - prev
if bucket > max:
max = bucket
return max
This algorithm only loops over the array once. Imagine having a fixed bucket sliding down an line. As you increment i, the bucket needs to take the most recent item, but the oldest item drops off the back. Using this logic, you only need to look at each item at most twice - when you add it to the bucket, and when you remove it out the other end.
** Please note that special case handling is omitted for the sake of clarity**
range(1, count - k+1)
len(inputArray) must also traverse the entire array to get its length" - that is false. All standard Python containers store their length.
sumcall iterates over all elements of its entire argument once - otherwise, it could not sum up those elements. What exactly is unclear to you about howsumworks?