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 万个元素)。这个问题有有效的解决方案吗？谢谢!

编辑:为了澄清，我需要保留每个组的第一个元素，而不是最小的元素(即[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)。如果不是，您可以将其添加到结果中，然后更新接近数字的集合。