高效的双重乘积求和
高效的双重乘积求和
考虑两个长度为n的ndarrays，arr1和arr2。我正在计算以下的乘积和，并且重复num_runs次以进行基准测试：
import numpy as np
import time
num_runs = 1000
n = 100
arr1 = np.random.rand(n)
arr2 = np.random.rand(n)
start_comp = time.clock()
for r in xrange(num_runs):
sum_prods = np.sum( [arr1[i]*arr2[j] for i in xrange(n)
for j in xrange(i+1, n)] )
print "总的推导时间 = ", time.clock() - start_comp
start_loop = time.clock()
for r in xrange(num_runs):
sum_prod = 0.0
for i in xrange(n):
for j in xrange(i+1, n):
sum_prod += arr1[i]*arr2[j]
print "总的循环时间 = ", time.clock() - start_loop
输出结果为
总的推导时间 = 3.23097066953
总的循环时间 = 3.9045544426
因此，使用列表推导似乎更快。是否有更高效的实现方式，例如使用Numpy的函数来计算这样的乘积和呢？
Efficient Double Sum of Products是一个问题，需要在给定两个数组arr1和arr2的情况下，计算出所有arr1[i]*arr2[j]的和，其中i 在给出的内容中，首先给出了一种使用向量化的方法来解决这个问题，即np.sum(np.triu(np.multiply.outer(arr1,arr2),1))。这种方法利用了NumPy库提供的函数，先使用np.outer(arr1,arr2)计算出arr1和arr2的外积，再使用np.triu()函数获取上三角矩阵，最后使用np.sum()函数计算和。这种方法的运行时间为272微秒。 接下来，给出了另外两种解决方法。第二种方法是使用循环来计算和，即使用[arr1[i]*arr2[j] for i in range(n) for j in range(i+1, n)]。这种方法的运行时间为7.9毫秒，比向量化方法慢了30倍。第三种方法是使用Numba库提供的jit装饰器来加速循环计算，即使用@jit装饰器修饰一个函数，然后在函数中使用循环计算和。这种方法的运行时间为21.1微秒，比第二种方法快了10倍。 最后，给出了一种更加简洁的解决方法。这种方法使用一个新的循环来计算和，即使用for循环遍历arr1的索引，然后使用一个变量c来记录arr2的累加和，最后计算arr1[i]*c的和。这种方法的运行时间为2.33微秒，比第三种方法快了10倍。同时，这种方法不涉及任何中间数组的创建。 总结起来，Efficient Double Sum of Products问题的出现是因为需要计算两个数组的元素乘积的和，其中满足一定条件的元素乘积需要被考虑。为了解决这个问题，可以使用向量化方法、循环计算方法或者Numba加速方法来提高计算效率。其中，使用Numba加速方法是最快的，并且不需要创建任何中间数组。
Efficient Double Sum of Products（高效的双重乘积和求和）问题出现的原因是希望将一个原本时间复杂度为O(n^2)的操作，重新排列为一个时间复杂度为O(n)的算法，并且利用NumPy来进行乘积和求和运算。
为了解决这个问题，可以使用以下代码：
# arr1_weights[i] 是原始版本中 arr1[i] 被乘以的所有 arr2[i] 的和 arr1_weights = arr2[::-1].cumsum()[::-1] - arr2 sum_prods = arr1.dot(arr1_weights)
根据计时结果，这种方法在n == 100时比列表推导的方法要快大约200倍。
In [21]: %%timeit ....: np.sum([arr1[i] * arr2[j] for i in range(n) for j in range(i+1, n)]) ....: 100 loops, best of 3: 5.13 ms per loop In [22]: %%timeit ....: arr1_weights = arr2[::-1].cumsum()[::-1] - arr2 ....: sum_prods = arr1.dot(arr1_weights) ....: 10000 loops, best of 3: 22.8 µs per loop
通过重新排列项，也可以用以下代码表示： arr1[:-1].cumsum().dot(arr2[1:])。
Efficient Double Sum of Products（高效的双重乘积求和）是一个问题，它要解决的是在计算两个数组的双重乘积求和时的效率问题。下面将介绍该问题的出现原因以及解决方法。
在给出的代码中，首先使用了numpy的广播技巧来计算两个数组arr1和arr2的双重乘积求和。具体的做法是通过将arr1和arr2进行广播，然后对广播后的数组进行逐元素相乘，最后再对相乘的结果进行求和。这样做的好处是利用了numpy在底层代码中实现的广播/向量化技术，从而提高了计算速度。
然后，通过对比计算结果和计时结果可以得出，使用广播技巧的方式比使用循环的方式更加高效。在给定的示例中，使用广播技巧的计算速度是使用循环的方式的约26倍。这是由于广播技巧利用了底层代码的优化，能够更快地执行计算。
另外，为了节省内存空间，可以使用另一种稍微慢一些的方法来计算双重乘积求和。具体的做法是利用numpy的triu_indices函数生成上三角矩阵的索引，然后使用np.dot函数对arr1和arr2的对应元素进行乘积计算，并将结果存储在output中。这种方法的好处是节省了内存空间，但计算速度相对较慢。
Efficient Double Sum of Products问题的出现是由于在计算两个数组的双重乘积求和时效率较低。为了解决这个问题，可以使用numpy的广播技巧来提高计算速度，或者使用triu_indices函数和np.dot函数来节省内存空间。通过对比计算结果和计时结果可以得出，使用广播技巧的方式更加高效。