Khi tôi gặp phải vấn đề tương tự. Sự khác biệt duy nhất là tôi phải giữ lại các đoạn thẳng trong danh sách một cách hiệu quả. Đó là một mô phỏng Monte-Carlo. Và các đoạn đường mới được tạo ngẫu nhiên phải được thêm vào các đoạn đường được sắp xếp và sắp xếp hiện tại.
Tôi đã điều chỉnh thuật toán cho vấn đề của bạn bằng cách sử dụng câu trả lời bằng cách lunixbochs để chuyển đổi IP thành số nguyên.
Giải pháp này cho phép thêm dải IP mới vào danh sách dải ô đã hợp nhất hiện có (trong khi các giải pháp khác dựa vào việc sắp xếp danh sách sắp xếp hợp nhất và không cho phép thêm dải ô mới đã được hợp nhất danh sách phạm vi). Nó được thực hiện theo chức năng add_range bằng cách sử dụng mô-đun bisect để tìm vị trí chèn dải IP mới và sau đó xóa các khoảng IP dự phòng và chèn phạm vi mới với các ranh giới được điều chỉnh để phạm vi mới bao trùm tất cả các dải ô đã xóa.
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))
Output:
['1.1.1.1-1.1.1.25', '2.2.2.2-2.2.2.10', '3.3.3.3-3.3.3.3']
Đây là rất nhiều niềm vui cho tôi để viết mã! Cảm ơn bạn vì điều đó :)
Sắp xếp và sau đó củng cố âm thanh như một giải pháp khá tốt đối với tôi. O (nlg (n)). Không chắc chắn nếu điều này có thể được cải thiện. –
@ColinD Tôi chắc chắn anh ấy muốn tránh đi từ phạm vi đến danh sách – agf