Loop with a Zero Execution Time

Why does the for loop execute one more time than the body of the loop?

That is because there is always one more evaluation of the condition of the loop than there are executions of the body of the loop.

Take this simple example:

x = 4
while x < 0:
    x += 1
    print('hello')

We can see that the body of the loop is never executed (0 times), while the exit condition of the loop is evaluated once(1 time).

So, in any situation, we have the following:

The body of the loop is executed once for every time the condition is evaluated to True
AND

The condition is one more time evaluated to False, for the program to exit the loop.

does sum() take the execution time of a loop in python3

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!

Better implementation

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!

Other options

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.

How much time does it take to execute a loop?

Here you can try this:

long startTime = System.currentTimeMillis();
long endTime = 0;

    for(int i=0; i < 1000000; i++) {

    //Something

    }

endTime = System.currentTimeMillis();

long timeneeded =  ((startTime - endTime) /1000);

How to reduce execution time in algorithm by replacing for loop in python

You can try to use numpy.cumsum and get the average dividing by the index+1 of the cumsum list.

import numpy as np

l =  [100, 20, 50, 70, 45]

l_cumsum = np.cumsum(l)
l_indices = np.arange(1,len(l)+1,1)
l_average = np.divide(l_cumsum, l_indices).tolist()

print(l_average) # Outputs [100.0, 60.0, 56.666666666666664, 60.0, 57.0]

It should be pretty fast, O(n), since numpy.cumsum is very optimized already. If you still want it faster you could multithread it.

python - time to execute a loop increases suddenly

Have you looked at the actual values involved?

The first triangular number with more than 47 factors is T(104) = 5460, which has 48 factors.

But the first triangular number with more than 48 factors is T(224) = 25200, which has 90 factors. So no wonder it takes a lot more work.

If your code runs up to T(n), then it calls range 2n times and fac n times, for a total of 3n function calls. Thus for T(104) it requires 312 function calls, and for T(224) it requires 672 function calls. Presumably there are 2 function calls of overhead somewhere that you're not showing us, which explains the profiling results you get.

---

Your current strategy is not going to get you to the answer for the Project Euler problem. But I can give some hints.

• Do you have to start over again with summ=0 each time you compute a triangular number?
• Do you have to loop over all the numbers up to n in order to work out how many divisors it has? Could there be a quicker way? (How many divisors does 2¹⁶ = 65536 have? Do you have to loop over all the numbers from 1 to 65536?)
• How many divisors do triangular numbers have? (Look at some small triangular numbers where you can compute the answer.) Can you see any patterns that would help you compute the answer for much bigger triangular numbers?

---

Related Topics