重複する可能性がある、または重複しない可能性がある IP 範囲 (前項のみ) のリストがあるとします。
('1.1.1.1-7', '2.2.2.2-10', '3.3.3.3-3.3.3.3', '1.1.1.4-25', '2.2.2.4-6')
重複する範囲を特定し、それらを単一の範囲に統合する方法を探しています。
('1.1.1.1-25', '2.2.2.2-10', '3.3.3.3-3')
アルゴリズムの現在の考えは、すべての範囲をすべての IP のリストに展開し、重複を排除し、並べ替え、連続する IP を統合することです。
他に Python 風のアルゴリズムの提案はありますか?
これがモジュールとしての私のバージョンです。私のアルゴリズムは、彼の回答で lunixbochs が言及したものと同一であり、範囲文字列から整数への変換とその逆の変換は適切にモジュール化されています。
import socket, struct
def ip2long(ip):
packed = socket.inet_aton(ip)
return struct.unpack("!L", packed)[0]
def long2ip(n):
unpacked = struct.pack('!L', n)
return socket.inet_ntoa(unpacked)
def expandrange(rng):
# expand '1.1.1.1-7' to ['1.1.1.1', '1.1.1.7']
start, end = [ip.split('.') for ip in rng.split('-')]
return map('.'.join, (start, start[:len(start) - len(end)] + end))
def compressrange((start, end)):
# compress ['1.1.1.1', '1.1.1.7'] to '1.1.1.1-7'
start, end = start.split('.'), end.split('.')
return '-'.join(map('.'.join,
(start, end[next((i for i in range(4) if start[i] != end[i]), 3):])))
def strings_to_ints(ranges):
# turn range strings into list of lists of ints
return [map(ip2long, rng) for rng in map(expandrange, ranges)]
def ints_to_strings(ranges):
# turn lists of lists of ints into range strings
return [compressrange(map(long2ip, rng)) for rng in ranges]
def consolodate(ranges):
# join overlapping ranges in a sorted iterable
iranges = iter(ranges)
startmin, startmax = next(iranges)
for endmin, endmax in iranges:
# leave out the '+ 1' if you want to join overlapping ranges
# but not consecutive ranges.
if endmin <= (startmax + 1):
startmax = max(startmax, endmax)
else:
yield startmin, startmax
startmin, startmax = endmin, endmax
yield startmin, startmax
def convert_consolodate(ranges):
# convert a list of possibly overlapping ip range strings
# to a sorted, consolodated list of non-overlapping ip range strings
return list(ints_to_strings(consolodate(sorted(strings_to_ints(ranges)))))
if __name__ == '__main__':
ranges = ('1.1.1.1-7',
'2.2.2.2-10',
'3.3.3.3-3.3.3.3',
'1.1.1.4-25',
'2.2.2.4-6')
print convert_consolodate(ranges)
# prints ['1.1.1.1-25', '2.2.2.2-10', '3.3.3.3-3']
範囲を数値のペアに変換します。これらの関数は、個々の IP を整数値との間で変換します。
def ip2long(ip):
packed = socket.inet_aton(ip)
return struct.unpack("!L", packed)[0]
def long2ip(n):
unpacked = struct.pack('!L', n)
return socket.inet_ntoa(unpacked)
これで、各範囲のエッジを数値としてソート/マージし、IP に変換して適切な表現を得ることができます。時間範囲のマージに関するこの質問には、優れたアルゴリズムがあります。
1.1.1.1-1.1.1.2との文字列を解析1.1.1.1-2して、数値のペアにします。後者の形式の場合、次のことができます。
x = '1.1.1.1-2'
first, add = x.split('-')
second = first.rsplit('.', 1)[0] + '.' + add
pair = ip2long(first), ip2long(second)
単純な数値比較を使用して、重複する範囲をマージします。
文字列表現に変換します (後者の形式を想定しています):
first, second = pair
first = long2ip(first) + '-' + long2ip(second).rsplit('.', 1)[1]
かつて私は同じ問題に直面しました。唯一の違いは、線分をリストに効率的に保持する必要があったことです。モンテカルロシミュレーション用でした。また、新しくランダムに生成された線分は、既存のソートおよびマージされた線分に追加する必要がありました。
lunixbochsの回答を使用してアルゴリズムを問題に適合させ、IP を整数に変換しました。
このソリューションでは、既にマージされている範囲の既存のリストに新しい IP 範囲を追加できます (一方、他のソリューションは、マージする範囲のリストをソートすることに依存しており、既にマージされている範囲リストに新しい範囲を追加することはできません)。add_rangeモジュールを使用しbisectて新しい IP 範囲を挿入する場所を見つけ、冗長な IP 間隔を削除し、新しい範囲がすべての削除された範囲を包含するように調整された境界で新しい範囲を挿入することによって機能的に行われます。
import socket
import struct
import bisect
def ip2long(ip):
'''IP to integer'''
packed = socket.inet_aton(ip)
return struct.unpack("!L", packed)[0]
def long2ip(n):
'''integer to IP'''
unpacked = struct.pack('!L', n)
return socket.inet_ntoa(unpacked)
def get_ips(s):
'''Convert string IP interval to tuple with integer representations of boundary IPs
'1.1.1.1-7' -> (a,b)'''
s1,s2 = s.split('-')
if s2.isdigit():
s2 = s1[:-1] + s2
return (ip2long(s1),ip2long(s2))
def add_range(iv,R):
'''add new Range to already merged ranges inplace'''
left,right = get_ips(R)
#left,right are left and right boundaries of the Range respectively
#If this is the very first Range just add it to the list
if not iv:
iv.append((left,right))
return
#Searching the first interval with left_boundary < left range side
p = bisect.bisect_right(iv, (left,right)) #place after the needed interval
p -= 1 #calculating the number of interval basing on the position where the insertion is needed
#Interval: |----X----| (delete)
#Range: <--<--|----------| (extend)
#Detect if the left Range side is inside the found interval
if p >=0: #if p==-1 then there was no interval found
if iv[p][1]>= right:
#Detect if the Range is completely inside the interval
return #drop the Range; I think it will be a very common case
if iv[p][1] >= left-1:
left = iv[p][0] #extending the left Range interval
del iv[p] #deleting the interval from the interval list
p -= 1 #correcting index to keep the invariant
#Intervals: |----X----| |---X---| (delete)
#Range: |-----------------------------|
#Deleting all the intervals which are inside the Range interval
while True:
p += 1
if p >= len(iv) or iv[p][0] >= right or iv[p][1] > right:
'Stopping searching for the intervals which is inside the Range interval'
#there are no more intervals or
#the interval is to the right of the right Range side
# it's the next case (right Range side is inside the interval)
break
del iv[p] #delete the now redundant interval from the interval list
p -= 1 #correcting index to keep the invariant
#Interval: |--------X--------| (delete)
#Range: |-----------|-->--> (extend)
#Working the case when the right Range side is inside the interval
if p < len(iv) and iv[p][0] <= right-1:
#there is no condition for right interval side since
#this case would have already been worked in the previous block
right = iv[p][1] #extending the right Range side
del iv[p] #delete the now redundant interval from the interval list
#No p -= 1, so that p is no pointing to the beginning of the next interval
#which is the position of insertion
#Inserting the new interval to the list
iv.insert(p, (left,right))
def merge_ranges(ranges):
'''Merge the ranges'''
iv = []
for R in ranges:
add_range(iv,R)
return ['-'.join((long2ip(left),long2ip(right))) for left,right in iv]
ranges = ('1.1.1.1-7', '2.2.2.2-10', '3.3.3.3-3.3.3.3', '1.1.1.4-25', '2.2.2.4-6')
print(merge_ranges(ranges))
出力：
['1.1.1.1-1.1.1.25', '2.2.2.2-2.2.2.10', '3.3.3.3-3.3.3.3']
これは私がコーディングするのがとても楽しかったです！有難うございます ：）
必要な場合に備えて、これらを横たわっていましたが、socket/structを使用する方がおそらく良い方法です
def ip_str_to_int(address):
"""Convert IP address in form X.X.X.X to an int.
>>> ip_str_to_int('74.125.229.64')
1249764672
"""
parts = address.split('.')
parts.reverse()
return sum(int(v) * 256 ** i for i, v in enumerate(parts))
def ip_int_to_str(address):
"""Convert IP address int into the form X.X.X.X.
>>> ip_int_to_str(1249764672)
'74.125.229.64'
"""
parts = [(address & 255 << 8 * i) >> 8 * i for i in range(4)]
parts.reverse()
return '.'.join(str(x) for x in parts)
IP の形式を統一し、範囲を int のペアに変換します。
これで、タスクははるかに簡単になりました - 整数範囲を「統合」します。私の素朴な試みの下に、それを行うための既存の効率的なアルゴリズムがたくさんあると思います：
>>> orig_ranges = [(1,5), (7,12), (2,3), (13,13), (13,17)] # should result in (1,5), (7,12), (13,17)
>>> temp_ranges = {}
>>> for r in orig_ranges:
temp_ranges.setdefault(r[0], []).append('+')
temp_ranges.setdefault(r[1], []).append('-')
>>> start_count = end_count = 0
>>> start = None
>>> for key in temp_ranges:
if start is None:
start = key
start_count += temp_ranges[key].count('+')
end_count += temp_ranges[key].count('-')
if start_count == end_count:
print start, key
start = None
start_count = end_count = 0
1 5
7 12
13 17
一般的な考え方は次のとおりです。(dict で) 範囲を別の範囲に配置した後temp_ranges、元の範囲の開始と終了を数えるだけで、新しい構成された範囲を見つけることができます。平等になると、統一された範囲が見つかりました。