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

Question

我有一个值列表，可能看起来像这样:[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 万个元素)。这个问题有有效的解决方案吗？谢谢!

编辑:澄清一下，我需要保留每个组的 first 元素，而不是最小的元素(即 [499, 702, 807] 不会上例中的有效结果)，因此对其进行排序可能没有太大帮助。

Answer 1

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)。如果不是，则将其添加到结果中，然后更新接近数字集。