Looping занимает слишком много времени в Python-3

Question

Я новичок в python. Старался решить проблему, но застревал из-за TLE. Следующий код занимает слишком много времени, около 10 секунд. Теперь мне интересно, насколько нормальная вложенная петля настолько неэффективна, или я делаю что-то неправильно?

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);  

Выход приведенного выше код:

0:00:10.595463 

Я уже знаю, что питон основан на переводчик и медленно, чем языки как C++ или Java. Но это много!

Поскольку индексирование python выполняется в O (1), это не займет много времени.

Пожалуйста, помогите мне понять, если это нормальное поведение python или что-то нужно изменить здесь.

Хотя я могу использовать numpy, но хочу использовать это в родном виде. Пожалуйста помоги.

Answer 1

Есть вещи для улучшения, хотя петли Python вложены довольно медленно, используя интерпретатор по умолчанию.

Для сценария, как это, вы могли бы попробовать Pypy вместо CPython :)

Мои результаты запущенный скрипт:

$ python3 script.py 
0:00:07.167943 

$ pypy script.py 
0:00:00.150436 

In this other question вы можете найти экспликации, почему существует такая большая разница в время между ними.

PD: Пожалуйста, не используйте точку с запятой в конце каждого оператора

Answer 2

Подъемное умножения из суммы повышает скорость значительно:

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 

Это примерно в 10 раз быстрее, чем время, которое вы опубликовали.

---

Но вы должны действительно использовать numpy для хруста.

Ниже я сделал straightforwad преобразование расчета выше 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