python - numpy 排序和删除最高值

Question

我不知道这个算法是否有名字，但基本上对于给定的y，我想找到最大值x，这样：

import numpy as np
np_array = np.random.rand(1000, 1)
np.sum(np_array[np_array > x] - x) >= y

当然，搜索算法将找到最高值n_1，将其减少到第二大值 ，n_2。停止如果n_1 - n-2 > y；否则将两者都归约n_1到n_2，如果...n_3则停止(n_1 - n_3) + (n_2 - n_3) > y

但我觉得必须有一个算法来生成一个x收敛到其真实值的 { s} 序列。

标签： pythonalgorithmnumpysorting

Answer 1

这是对原始问题的回答，我们在其中找到了最大值xst np.sum(np_array[np_array > x]) >= y：

您可以通过排序和累积总和来完成此操作：

s = np.sort(np_array)[::-1]
c = np.cumsum(s)
i = np.argmax(c > y)

result = s[i]

sx是按降序排列的候选人。比较累积总和c可以y告诉您总和将超过的确切位置y。np.argmax返回第一个发生的位置的索引。结果是从 中提取的索引s。

numpy 中的这种计算比它需要的要慢，因为我们可以立即短路总和而无需计算单独的掩码。然而，复杂性是相同的。您可以使用 numba 或 cython 加速以下操作：

s = np.sort(np_array)[::-1]
c = 0
for i in range(len(s)):
    c += s[i]
    if c > y:
        break
result = s[i]