列表中夫妇的乘积之和

问题描述

我想在列表中找出情侣乘积的和。 例如，给出了一个[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

让xs = a1, a2, .., an，然后

(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的方法和我的方法

结果和测试代码如下(时间越短越好)：

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