Python: finding a list of numbers in a list of very large numbers, allowing a + or - 5 error

Question

Situation:

I want to do a comparison: check if the number is in the list of numbers (a very large list, the length is over 1e ^ 5 or even 2e ^ 5), allowing a + or - 5 error

Example: match 95 on the list [0, 15, 30, 50,60,80,93] → true match 95 on the list [0,15,30,50,60,70,80,105,231,123123,12312314, ...] → false

ps: the list is not sorted (or I can sort it if in this way the efficiency can be increased)

I tried using a dictionary (somekey and list of numbers), but it was too slow when I search the list.

Are there any better ideas? (there are 3000+ numbers that I need to find)

Answer 1

If you need to complete many queries, you can simply create a set and search in

>>> 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

Creation setis O (n), of course, but now lookups are O (1)

Answer 2

Without sorting the list (time O (n)) :

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

Sort (O (nlogn) time to sort + O (logn) search time) :

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)

Answer 3

@inspectorG4dget , :

( ),

(, ), , , .

, . Python bisect .

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)