- I have an IP address. For example, 192.168.2.10
- Also I have a dictionary:
RANGES = { 'london': [ {'start': '10.10.0.0', 'end': '10.10.255.255'}, {'start': '192.168.1.0', 'end': '192.168.1.255'}, ], 'munich': [ {'start': '10.12.0.0', 'end': '10.12.255.255'}, {'start': '172.16.10.0', 'end': '172.16.11.255'}, {'start': '192.168.2.0', 'end': '192.168.2.255'}, ] }
Question: How should I find the city from my IP address and use this dictionary spending less time (time complexity) as possible?
Advertisement
Answer
The “proper answer” if you want the best complexity for arbitrarily large data sets is the one given given by Ji Bin.
To really optimize performances over multiple calls, you indeed need to restructure your data, and use the inbuilt bisect function.
But if you REALLY do not want to touch your data, you can still use a band-aid custom implementation of bisect which would look like that
RANGES = { 'london': [ {'start': '10.10.0.0', 'end': '10.10.255.255'}, {'start': '192.168.1.0', 'end': '192.168.1.255'}, ], 'munich': [ {'start': '10.12.0.0', 'end': '10.12.255.255'}, {'start': '172.16.10.0', 'end': '172.16.11.255'}, {'start': '192.168.2.0', 'end': '192.168.2.255'}, ] } def ipv4_str_to_tuple(ip_str): return tuple(map(int, ip_str.split('.'))) def relative_in_range(ipv4_tuple, ip_range): ipv4t_start = ipv4_str_to_tuple(ip_range['start']) ipv4t_end = ipv4_str_to_tuple(ip_range['end']) if ipv4t_start > ipv4_tuple: return -1 if ipv4t_end < ipv4_tuple: return 1 return 0 def from_those_ranges(ipv4_tuple, ranges): #in-built bisect lo, hi = 0, len(ranges) while lo < hi: mid = lo + (hi - lo) // 2 comp = relative_in_range(ipv4_tuple, ranges[mid]) if comp == 0: return True if comp > 0: lo = mid + 1 else: hi = mid return False def find_entry_from_ipv4_tuple(ipv4_tuple, entries_ranges): for entry, entry_ranges in entries_ranges.items(): if from_those_ranges(ipv4_tuple, entry_ranges): return entry return None def find_entry_from_ipv4_str(ipv4_str, entries_ranges): ipv4_tuple = ipv4_str_to_tuple(ipv4_str) return find_entry_from_ipv4_tuple(ipv4_tuple, entries_ranges) print(find_entry_from_ipv4_str('10.2.4.2', RANGES)) print(find_entry_from_ipv4_str('192.168.2.1', RANGES)) print(find_entry_from_ipv4_str('192.168.1.1', RANGES)) print(find_entry_from_ipv4_str('172.12.10.25', RANGES)) print(find_entry_from_ipv4_str('192.168.2.1', RANGES)) print(find_entry_from_ipv4_str('10.10.5.5', RANGES))
-> None
-> munich
-> london
-> None
-> munich
-> london
etc.
link to playground : https://trinket.io/python/e1f9deb1c7