时间戳

首页 > 解决方案 > 仅保留远距离值的有效算法

python - 仅保留远距离值的有效算法

问题描述

我有一个可能看起来像这样的值列表：[500,501,809,702,808,807,703,502,499]并且我只想将每个数字的第一个实例保持在一定距离内。换句话说，我想得到这个列表：[500,809,702]因为其他数字与这些数字有一定的距离。所以它会保留 500，跳过 501 因为它太近了，保留 809 因为它远离已经选择的值，保留 702，等等。

这是我目前的解决方案：

vals = ... #the original data
result = []
tolerance = 50
for i in vals:
    if not len(np.where(np.abs(result - i) < tolerance)[0]):
        results.append(i)

这很好用，但对于我的目的来说太慢了（我正在处理列表中的 240 万个元素）。这个问题有有效的解决方案吗？谢谢！

编辑：为了澄清，我需要保留每个组的第一个元素，而不是最小的元素（即[499, 702, 807]在上面的示例中不是有效的结果），因此对其进行排序可能没有太大帮助。

标签： pythonalgorithm

解决方案

vals = [500,501,809,702,808,807,703,502,499]
close_set = set()
tolerance = 5
result = []
for e in vals:
    if e in close_set:
        continue
    else:
        result.append(e)
        close_set.update([*range(e-tolerance, e+tolerance+1)])

print(result)  # [500, 809, 702]

这应该很快（我在 1,000,000 个元素的列表上对其进行了测试，大约需要 3 秒）。对于列表中的每个元素，您可以通过检查接近数字集合中的成员资格来检查是否以前看到过接近值，即 O(1)。如果不是，则将其添加到结果中，然后更新关闭数字集。

推荐阅读