Python：在一组非常大的数字中搜索一组数字，允许+或-5的误差。

Question

情况：

我想要进行匹配：检查一个数字是否在数字列表中（非常大的列表，长度超过1e^5甚至2e^5），允许+或-5的误差。

例子： 在列表[0，15，30，50，60，80，93]中匹配95 -> true 在列表[0，15，30，50，60，70，80，105，231，123123，12312314，...]中匹配95 -> false

注：列表未排序（如果按此方式排序，则可以提高效率）

我尝试使用字典（一些键和数字列表），但在列表中进行搜索时速度太慢。

有更好的想法吗？（我需要搜索3000多个数字）

- TYZ

---

当你说搜索时，是指单个到多个结果，一对一的结果还是多对多的结果？ 例如，在{10 15 20 25 30}列表中搜索15。你返回第一个找到的10，还是返回所有找到的结果？使用最后一个例子，假设你在15之后再次搜索10，你会再次返回10吗？ - Rusty Weber

你的意思是需要在同一个列表上搜索3000次吗？ - John La Rooy

你的数字是整数还是浮点数？你想要什么结果 - 对于每个搜索数字只是 True 或 False，还是匹配值？如果一个搜索数字匹配多个目标，你有任何偏好吗（例如，你想要最接近的匹配，还是任何匹配）？ - Hugh Bothwell

Answer 1

不排序列表（O(n)时间）：

def search(L, x):
    for i in L:
        if -5 <= i-x <= 5:
            return True
    return False

使用排序（O(nlogn)时间复杂度进行排序 + O(logn)时间复杂度进行搜索）：

def search(L, x):
    L.sort()
    return fuzzyBinSearch(L, x)

def fuzzyBinSearch(L, x):
    mid = len(L)/2
    i = L[mid]
    if if -5 <= i-x <= 5:
        return True
    elif i-x > 5:
        return fuzzyBinSearch(L[mid+1:], x)
    else:
        return fuzzeBinSearch(L[:mid], x)

- inspectorG4dget

---

如果您可以将5更改为类似于在fuzzyBinSearch之外定义的常量ACCEPTABLE_ERROR = 5，那就更好了。 - xis

Answer 2

如果您需要进行多次搜索，您可以创建一个集合并在其中搜索。

>>> L = [0, 15, 30, 50,60,80,93]
>>> S = {i+x for i in L for x in range(-5, 6)}
>>> 95 in S
True

创建set的时间复杂度为O(n)，但是现在查找的时间复杂度为O(1)。

- John La Rooy

Answer 3

我喜欢@inspectorG4dget的答案，但会进行改进：

不要对长列表进行排序和搜索（需要将其全部存储在内存中），

对要查找的数字进行短列表排序，然后迭代长列表，查看每个项是否与任何搜索项匹配。

这样应该更快，使用的内存也更少。您可能希望使用Python的bisect模块来实现此操作。

- Hugh Bothwell

Answer 4

a = set([0, 15, 30, 50,60,80,93])
def match(n):
    return bool({n+i for i in range(-5,6)} & a)
print match(95)

a = set([0,15,30,50,60,70,80,105,231,123123,12312314])
print match(95)

- Alvaro Fuentes