- 我有一個 IP 地址。例如，192.168.2.10
- 我還有一本字典：
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'},
]
}
問題：我應該如何從我的 IP 地址中找到城市并使用這本詞典盡可能減少時間（時間復雜度）？
uj5u.com熱心網友回復：
撰寫一個自定義函式，將 IP 地址決議為數字元組，以便于比較：
def get_city(ip):
for city in RANGES:
for d in RANGES[city]:
if tuple(map(int, d["start"].split("."))) <= tuple(map(int, ip.split("."))) <= tuple(map(int, d["end"].split("."))):
return city
>>> get_city("192.168.2.10")
"munich"
uj5u.com熱心網友回復：
首先，您需要重新排列資料，以便更有效地查找。
- 創建一個將 IP 地址轉換為數字的函式
- 并使用較低/起始 IP 號作為新的資料鍵，并將結束 IP 保留在值中。
def ip_to_long(ip):
return reduce(lambda x, y: (x << 8) y, map(int, ip.split('.')))
def data_transform(input_ranges):
data = {}
for location, items in RANGES.items():
for item in items:
data[ip_to_long(item['start'])] = dict(location=location, end=ip_to_long(item['end']))
現在，您可以使用bisect搜索排序的起始 IP，作為您的輸入，在內部使用 RB-tree 對其進行 AIK。
下面是它的完整 PoC 代碼：
from functools import reduce
from bisect import bisect_left
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 ip_to_long(ip):
return reduce(lambda x, y: (x << 8) y, map(int, ip.split('.')))
def data_transform(input_ranges):
data = {}
for location, items in input_ranges.items():
for item in items:
data[ip_to_long(item['start'])] = dict(location=location, end=ip_to_long(item['end']))
return data
def search_for_ip(search_ip, ip_starts, ip_data):
lookup_index = bisect_left(ip_starts, ip_to_long(search_ip))
if lookup_index > 0 and ip_data[ip_starts[lookup_index-1]]['end'] > ip_to_long(search_ip):
return ip_data[ip_starts[lookup_index-1]]['location']
return
new_data = data_transform(RANGES)
print(new_data)
ip_starts = sorted(list(new_data))
print(search_for_ip('192.168.2.100', ip_starts, new_data)) # -> munich
print(search_for_ip('192.168.1.100', ip_starts, new_data)) # -> lodon
print(search_for_ip('192.168.0.100', ip_starts, new_data)) # -> None
uj5u.com熱心網友回復：
如果您想要任意大資料集的最佳復雜性，“正確答案”是 Ji Bin 給出的答案。
要真正優化多次呼叫的性能，您確實需要重組資料，并使用內置的 bisect 函式。
但是，如果您真的不想觸摸您的資料，您仍然可以使用 bisect 的創可貼自定義實作，看起來像這樣
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))
-> 無
-> 慕尼黑
-> 倫敦
-> 無
-> 慕尼黑
-> 倫敦
etc.
link to playground : https://trinket.io/python/e1f9deb1c7
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/441194.html
標籤：Python python-3.x 表现 ip IP地址