これは古い問題です。会社の製品では、新しく追加された IP が既に存在するかどうかを頻繁にチェックする必要があります。そのためには、重複する IP を判断するアルゴリズムが必要です。ここでは、アルゴリズムの考え方だけを紹介します。
問題：与えられた IP またはネットワークセグメントがデータベースに既に存在するかどうかを判断する方法は？
- 最も単純なアルゴリズムは、すべてのネットワークセグメントをリストアップし、単一の IP に変換して個別に比較することです。この方法は最も一般的な方法であり、詳細は省略します。利点はシンプルで理解しやすいことですが、リソースを多く消費するという欠点があります。
- やや最適化された方法では、各 IP を数値として扱うことができます（2 進数を 10 進数に変換するだけです）。セグメントの場合は、開始と終了の 2 つの数値のみを記録し、重複を判断する必要がある IP に対して数値を比較します。各セグメントは 1 つのグループであり、個別に比較します。利点：ストレージリソースの最適化（O (n)）、欠点：複数回の走査と比較（T (n)）が存在します。
- もう少し最適化すると、セグメントごとに開始と終了の 2 つのポイントのみを記録し、すべてのセグメントを同じライン上に配置します。開始のポイントは 1 とし、終了のポイントは - 1 とします。このラインを先頭から順に加算し、毎回前の 2 つの値を取ります。
- 重複しないすべてのセグメントの場合、合計は 0 です。
- 重複するセグメントが存在する場合、合計は 0 ではありません。
キーポイントのコードを少し列挙します。
def get_first_last_ip(ip_cidr:str) -> list:
try:
ip, cidr = ip_cidr.split('/')
octets = ip.split('.')
subnet_bits = int(cidr)
# IPアドレスを32ビットのバイナリ文字列に変換
ip_binary = ''.join([bin(int(octet))[2:].zfill(8) for octet in octets])
# サブネットビット数に基づいてネットワークアドレスとブロードキャストアドレスのバイナリ文字列を計算
network_binary = ip_binary[:subnet_bits] + '0' * (32 - subnet_bits)
broadcast_binary = ip_binary[:subnet_bits] + '1' * (32 - subnet_bits)
# バイナリ文字列をIPアドレス形式に変換
start_ip = '.'.join([str(int(network_binary[i:i+8], 2)) for i in range(0, 32, 8)])
end_ip = '.'.join([str(int(broadcast_binary[i:i+8], 2)) for i in range(0, 32, 8)])
return [start_ip, end_ip]
except ValueError:
# logging.error("Invalid IP format")
return [None, None]
def check_ip_cover(ip:str) -> bool:
dic = build_ip_dic()
try:
if check_ip(ip) and valid_ip_netmask(ip):
[first_ip, last_ip] = get_first_last_ip(ip)
first_ip_num = ip_2_int(first_ip)
last_ip_num = ip_2_int(last_ip)
if first_ip_num not in dic:
dic[first_ip_num] = 1
else:
logging.info("IP {} is repeated.".format(first_ip))
return False
if last_ip_num not in dic:
dic[last_ip_num] = -1
else:
logging.info("IP {} is repeated.".format(last_ip))
return False
res = 0
## 辞書をソート
sorted_dic = sorted(dic.keys())
## 毎回2つの値を取り出して演算
## 合計が0でない場合は終了
ip_key_iter = iter(sorted_dic.keys())
while True:
try:
ip_1 = next(ip_key_iter)
ip_2 = next(ip_key_iter)
value_1 = sorted_dic[ip_1]
value_2 = sorted_dic[ip_2]
if value_1 + value_2 != 0:
return False
except StopIteration:
if ip_1:
return False
return True
except Exception as e:
logging.error("Some wrong in here: {}".format(e))
このアルゴリズムは非常に巧妙で、開始と終了の IP のみを見れば、大量の IP を重複チェックできます。
7/13 修正：
以前の内容にいくつかの論理的な問題があったため、少し修正しました。