我想找出列表中情侣的乘积之和。
例如给出一个列表[1, 2, 3, 4]。我想要得到的是答案=1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4.
我使用暴力来完成此操作，它会给我带来非常大的列表的超时错误。 我想要一种有效的方法来做到这一点。请告诉我，我该怎么做？
这是我的代码，这是有效的，但我需要更高效的代码：
def proSum(list):
count = 0
for i in range(len(list)- 1):
for j in range(i + 1, len(list)):
count += list[i] * list[j]
return count
这里是：
In [1]: def prodsum(xs):
...: return (sum(xs)**2 - sum(x*x for x in xs)) / 2
...:
In [2]: prodsum([1, 2, 3, 4]) == 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4
Out[2]: True
Let xs = a1, a2, .., an, then
(a1+a2+...+an)^2 = 2(a1a2+a1a3+...+an-1an) + (a1^2+...+an^2)
所以我们有
a1a2+...+an-1an = {(a1+a2+...+an)^2 - (a1^2+...+an^2)}/2
比较 @georg 的方法和我的方法的性能
The result and the test codes as following(The less time used is better):
In [1]: import timeit
In [2]: import matplotlib.pyplot as plt
In [3]: def eastsunMethod(xs):
...: return (sum(xs)**2 - sum(x*x for x in xs)) / 2
...:
In [4]: def georgMethod(given):
...: sum = 0
...: res = 0
...: cur = len(given) - 1
...:
...: while cur >= 0:
...: res += given[cur] * sum
...: sum += given[cur]
...: cur -= 1
...: return res
...:
In [5]: sizes = range(24)
In [6]: esTimes, ggTimes = [], []
In [7]: for s in sizes:
...: t1 = timeit.Timer('eastsunMethod(xs)', 'from __main__ import eastsunMethod;xs=range(2**%d)' % s)
...: t2 = timeit.Timer('georgMethod(xs)', 'from __main__ import georgMethod;xs=range(2**%d)' % s)
...: esTimes.append(t1.timeit(8))
...: ggTimes.append(t2.timeit(8))
In [8]: fig, ax = plt.subplots(figsize=(18, 6));lines = ax.plot(sizes, esTimes, 'r', sizes, ggTimes);ax.legend(lines, ['Eastsun', 'georg'], loc='center');ax.set_xlabel('size');ax.set_ylabel('time');ax.set_xlim([0, 23])