有没有办法通过不计算不必要的金额来节省时间？

Question

objective

给定一个二维数组 A，我必须不断将每列第一行的值加 +1，直到列的总和等于相同的值，例如 28。

我的解决方案

这可能不是最好的解决方案，但考虑到我要表达的观点，它会起作用。这是一个简化的示例。在原始版本中，它基于第一行或第二行获得 +1 的概率分布，并且列之间有所不同。而且还得一个一个做，因为概率分布的变化是因为一列的第一行还是第二行在上一个循环中得到了+1。所以列求和和迭代是必要的。

import numpy as np

A = np.arange(20).reshape(2, 10)
print(A)

MASK = A.sum(axis=0) < 28
print(A.sum(axis=0) < 28)

while np.any(MASK):
    LUCKYROW = np.repeat(0, np.count_nonzero(MASK))
    A[LUCKYROW, MASK] += 1
    MASK = A.sum(axis=0) < 28
    print(A.sum(axis=0) < 28)
print(A)

让我们看一下输出：

[[ 0  1  2  3  4  5  6  7  8  9]
 [10 11 12 13 14 15 16 17 18 19]]
[ True  True  True  True  True  True  True  True  True False]
[ True  True  True  True  True  True  True  True  True False]
[ True  True  True  True  True  True  True  True False False]
[ True  True  True  True  True  True  True  True False False]
[ True  True  True  True  True  True  True False False False]
[ True  True  True  True  True  True  True False False False]
[ True  True  True  True  True  True False False False False]
[ True  True  True  True  True  True False False False False]
[ True  True  True  True  True False False False False False]
[ True  True  True  True  True False False False False False]
[ True  True  True  True False False False False False False]
[ True  True  True  True False False False False False False]
[ True  True  True False False False False False False False]
[ True  True  True False False False False False False False]
[ True  True False False False False False False False False]
[ True  True False False False False False False False False]
[ True False False False False False False False False False]
[ True False False False False False False False False False]
[False False False False False False False False False False]
[[18 17 16 15 14 13 12 11 10  9]
 [10 11 12 13 14 15 16 17 18 19]]

好的，可以了，但是为什么每次循环都要计算每列的总和呢？根据之前的循环，我知道哪一列的总和已经达到了目标值。如果我利用这些信息，我也许可以节省时间。

我的第二个解决方案

import numpy as np

A = np.arange(20).reshape(2, 10)
print(A)

MASK = A.sum(axis=0) < 28
print(A.sum(axis=0) < 28)

while np.any(MASK):
    LUCKYROW = np.repeat(0, np.count_nonzero(MASK))
    A[LUCKYROW, MASK] += 1
    MASK[MASK] = A[:, MASK].sum(axis=0) < 28
    print(A[:, MASK].sum(axis=0) < 28)
print(A)

输出：

[[ 0  1  2  3  4  5  6  7  8  9]
 [10 11 12 13 14 15 16 17 18 19]]
[ True  True  True  True  True  True  True  True  True False]
[ True  True  True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True]
[ True  True  True  True  True  True  True]
[ True  True  True  True  True  True]
[ True  True  True  True  True  True]
[ True  True  True  True  True]
[ True  True  True  True  True]
[ True  True  True  True]
[ True  True  True  True]
[ True  True  True]
[ True  True  True]
[ True  True]
[ True  True]
[ True]
[ True]
[]
[[18 17 16 15 14 13 12 11 10  9]
 [10 11 12 13 14 15 16 17 18 19]]

似乎有效。虽然出现了一个问题。它比第一个解决方案不快。我尝试过使用 25000 列和 74998 作为目标值，但它们在时间上大致相等。

我的要求

我想我可能对 ndarray 操作或 ndarray 索引有根本性的误解。第二种解决方案应该在每个循环中进行越来越少的计算，因此我预计性能会有显着提高。我找不到解释。我的思路错在哪里？

Answer 1

由于您只更改第一行，因此无需在每次迭代时重新计算列的总和。事实上，由于唯一的变化是将 1 添加到第一行的某些元素，因此您根本不需要迭代。

A = np.arange(20).reshape(2, 10)
s = A.sum(0)
d = max(s) - s
A[0] += d

>>> A
array([[18, 17, 16, 15, 14, 13, 12, 11, 10,  9],
       [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]])

对于更复杂的计算，这可能是不可能的，但对于求和，这是一个简单的捷径。

您的 "faster" 代码实际上运行速度不快可能有几个原因。首先，感谢您实际分析代码。第一个原因是 A 很小。通常，numpy 仅在数组中包含数千或数万个元素时才提供速度优势。

其次，在 "faster" 代码行

MASK[MASK] = A[:, MASK].sum(axis=0) < 28

创建 A 中由 MASK 索引的所有行的副本。这可能是一个相当昂贵的操作，因此使用 MASK = A.sum(axis=0) < 28 对原始版本中的额外行求和可能更快，因为它不需要额外的副本。

Answer 2

索引如何影响总和的快速演示：

In [140]: x = np.arange(10000)                                                       
In [141]: timeit x.sum()                                                             
13.4 µs ± 183 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

对一半的项目求和，即使使用快速切片 view 也不会节省那么多时间：

In [142]: timeit x[:5000].sum()                                                      
10.8 µs ± 78.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

高级索引或屏蔽速度较慢：

In [143]: %%timeit idx=np.arange(5000) 
     ...: x[idx].sum() 

21.3 µs ± 1.12 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [144]: %%timeit 
     ...: x[x<=5000].sum() 

34.4 µs ± 1.34 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

在现代计算机上，像加法这样的基本数学并不那么昂贵。选择项目并遍历数组在时间上与添加本身一样昂贵。

有没有办法通过不计算不必要的金额来节省时间？

Is there a way to save time by not calculating unnecessary sums?

python

performance

numpy

python-3.x

numpy-ndarray

objective

我的解决方案

我的第二个解决方案

我的要求