在Python-3中循环花费了太多的时间。

Question

我对蟒蛇很陌生。试图解决一个问题但由于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

我已经知道python是基于解释器的，比C++或Java这样的编译语言慢。但这可是太多了！

由于python索引是在O(1)中完成的，所以这不需要花费太多时间。

如果这是python的正常行为，或者这里需要更改的任何东西，请帮助我理解。

虽然我可以用numpy，但想用这个本地的方式。请帮帮忙。

Answer 1

虽然Python嵌套循环使用默认解释器的速度非常慢，但仍有一些需要改进的地方。

对于这样的脚本，您可以尝试皮皮而不是CPython :)

我的结果运行了您的脚本：

$ python3 script.py
0:00:07.167943

$ pypy script.py
0:00:00.150436

在另一个问题上可以解释为什么两者之间的运行时有如此大的差异。

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进行数字处理。

下面，我直接将上面的计算转换为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