Looping taking too much time in Python-3

Question

I am new to python. Was trying to solve a problem but stuck due to TLE. The following code is taking too much time, around 10 sec. Now, I'm wondering if normal nested looping is so much inefficient or I am doing something wrong?

from datetime import datetime

arr = [1 for i in range(10000)]; # Originally had large size array of length ~10^4 
l = len(arr);
ans = 0;
time1 = datetime.now();
# arr = sorted(arr);
for i in range(l):    
    for j in range(i+1,l):        
        ans+= arr[i]*arr[j];
print(datetime.now() - time1);

The output to the above code:

0:00:10.595463

I already know that python is based on interpreter and is slow than compiled languages like C++ or Java. But this is a lot!

Since python indexing is done in O(1), this shouldn't take so much time.

Please help me understand if this is normal behaviour of python or anything needs to be changed here.

Although I can use numpy but want to use this in native fashion. Please help.

If you work out the number of steps that you are taking: 10000 loops with 99999 loops decreasing it is not that surprising that it takes some time to execute 3*49995000 lines of code. — Steve Barnes, Feb 19 '17 at 08:04
https://repl.it/FpH9/1 - edited version drops runtime on repl.it from 11.5 seconds to 6.5 seconds, ish. — TessellatingHeckler, Feb 19 '17 at 08:09
And python is notoriously bad for numerical calculations in itself - for number crunching one really must use numpy. — Antti Haapala -- Слава Україні, Feb 19 '17 at 08:09
@TessellatingHeckler Very useful that is!! Can you explain the reason behind that improvement. — Neetesh Dadwariya, Feb 19 '17 at 08:29
@JavaFreak not exactly, but going `get next thing, next thing, next thing` is nice and Pythonic, and going `count 1, get thing[counter], count 2, get thing [counter], count 3, get thing[counter]` is more laborious. The first one, the counting/indexing is done behind the scenes in the CPython engine, the second one it's done with the overhead of interpreting the Python code. That's one typical way to speed up Python code, push the work down the stack to the lower (faster) levels - as Roland Smith does way way better with `sum(arr[j+1:])`. — TessellatingHeckler, Feb 19 '17 at 21:34

score 1 · Answer 1 · edited May 23 '17 at 12:00

There are things to improve, although Python nested loops are quite slow using the default interpreter.

For a script like this, you could try Pypy instead of CPython :)

My results runnig your script:

$ python3 script.py
0:00:07.167943

$ pypy script.py
0:00:00.150436

In this other question you can find an explication for why there's such a big difference in runtimes between both.

PD: Please don't use semicolons at the end of each statement

Roland Smith · Answer 2 · 2017-02-19T10:18:05.387

Lifting the multiplication out of the sum improves the speed considerably:

In [1]: arr = [1 for i in range(10000)]

In [2]: def calc2(arr):
   ...:     ans = 0
   ...:     for j in range(len(arr)):
   ...:         ans += arr[j] * sum(arr[j+1:])
   ...:     return ans
   ...: 

In [3]: %timeit calc2(arr)
1 loop, best of 3: 1.02 s per loop

This is about 10x faster than the time you posted.

But you should really use numpy for number crunching.

Below I've done a straightforwad conversion of the calculation above to numpy:

In [1]: import numpy as np

In [2]: def calc(arr):
   ...:     ans = np.zeros_like(arr)
   ...:     for j in range(len(arr)):
   ...:         ans[j] = arr[j] * np.sum(arr[j+1:])
   ...:     return np.sum(ans)
   ...: 

In [3]: arr = np.random.rand(10000)

In [4]: %timeit calc(arr)
1 loop, best of 3: 181 ms per loop

Looping taking too much time in Python-3

2 Answers2