views:

87

answers:

3

I have 1M numbers:N[], and 1 single number n, now I want to find in those 1M numbers that are similar to that single number, say an area of [n-10, n+10]. what's the best way in python to do this? Do I have to sort the 1M number and do an iteration? Thanks

+3  A: 

[x for x in N if n - 10 <= x <= n + 10]

isbadawi
will this do an whole 1M number iteration?
Yes, it's still a loop behind the scenes.
isbadawi
+1  A: 
results=[x for x in numbers if x >= n-10 and x <= n+10]
S.Mark
`results=[(i, x) for i, x in enumerate(numbers) if x >= n-10 and x <= n+10]` if you want to keep track of the indices of the similar numbers.
Mike DeSimone
Python supports chained comparison operators like `n - 10 <= x <= n + 10`
Mike Graham
A: 

Another solution:

is_close_to_n = lambda x: n-10 <= x <= n+10
result = filter(is_close_to_n, N)

Generalizing a bit:

def is_close_to(n):
    f = lambda x: n-10 <= x <= n+10
    return f

result12 = filter(is_close_to(12), N)
result123 = filter(is_close_to(123), N)

Do not sort. Sorting is, in general, O(n log n); brute-force searching is O(n).

Federico Ramponi
Thanks, What if I have those numbers sorted? Is there a O(log n) and simple solution for this? like do a binary search? Do python have some thing like "self defined compare function"?
If the list is already sorted, you can use binary search to find the index i1 of the first element >=n-10. Then proceed forward (in a while loop) to find the index i2 of the first element >n+10. N[i1:i2] should then be what you're loking for. What do you mean by "self defined compare function"?
Federico Ramponi
I mean if have a library function like thisbinary_search(N,n,cmp=mycompare)def mycompare(x,n): if n-10<x<n+10: return true else return false
bisect module might also also help, if they're sorted.
Gregg Lind