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
will this do an whole 1M number iteration?
2010-04-02 03:55:53
Yes, it's still a loop behind the scenes.
isbadawi
2010-04-02 04:02:42
`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
2010-04-02 03:55:48
Python supports chained comparison operators like `n - 10 <= x <= n + 10`
Mike Graham
2010-04-02 04:03:20
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
2010-04-02 03:56:31
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"?
2010-04-02 04:08:48
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
2010-04-02 04:13:47