如何在Numpy数组中找到M个元素的N个最大乘积子数组？

Question

我有一个Numpy数组，需要找到M个元素的最大乘积子数组的前N个。例如，我有数组p = [0.1, 0.2, 0.8, 0.5, 0.7, 0.9, 0.3, 0.5]，我想要找到三个元素的五个最高乘积子数组。有没有"快速"的方法可以实现这个目标？

- Andrea Belle

---

这不是一个numpy数组。 - Mad Physicist

你在发布的解决方案中有没有一个可用？ - Divakar

Answer 1

这是另一种快速的方法：

import numpy as np

p = [0.1, 0.2, 0.8, 0.5, 0.7, 0.9, 0.3, 0.5]
n = 5
m = 3

# Cumulative product (starting with 1)
pc = np.cumprod(np.r_[1, p])
# Cumulative product of each window
w = pc[m:] / pc[:-m]
# Indices of the first element of top N windows
idx = np.argpartition(w, n)[-n:]
print(idx)
# [1 2 5 4 3]

- jdehesa

---

这个想法很好。只是对于相当大的数组，并且其中包含分数，最终会在后面产生零。 - Divakar

@Divakar 是的，这是一个很好的观点，如果数组足够大，那么精度可能会受到影响，如果不是，那么性能可能也不是一个问题。 - jdehesa

Answer 2

方法 #1

我们可以创建滑动窗口，然后执行prod缩减，最后使用np.argpartition来获取其中前N个 -

from skimage.util.shape import view_as_windows

def topN_windowed_prod(a, W, N):
    w = view_as_windows(a,W)
    return w[w.prod(1).argpartition(-N)[-N:]]

样例运行 -

In [2]: p = np.array([0.1, 0.2, 0.8, 0.5, 0.7, 0.9, 0.3, 0.5])

In [3]: topN_windowed_prod(p, W=3, N=2)
Out[3]: 
array([[0.8, 0.5, 0.7],
       [0.5, 0.7, 0.9]])

请注意，np.argpartition 不会维护顺序。因此，如果我们需要按 prod 值的降序获取前 N 个值，请使用 range(N)。 更多信息。 方法 #2 对于较短的窗口长度，我们可以简单地切片并获取所需的结果，如下所示 -

def topN_windowed_prod_with_slicing(a, W, N):
    w = view_as_windows(a,W)
    L = len(a)-W+1
    acc = a[:L].copy()
    for i in range(1,W):
        acc *= a[i:i+L]
    idx = acc.argpartition(-N)[-N:]
    return w[idx]

- Divakar