एक बार मैं एक ही समस्या का सामना करना पड़ा। केवल अंतर यह था कि मुझे सूची में लाइन सेगमेंट को कुशलता से रखना था। यह एक मोंटे कार्लो सिमुलेशन के लिए था। और नए यादृच्छिक रूप से जेनरेट किए गए लाइन सेगमेंट को मौजूदा सॉर्ट और विलय लाइन सेगमेंट में जोड़ा जाना था।
मैंने lunixbochs द्वारा आईपी को पूर्णांक में बदलने के लिए उत्तर का उपयोग करके आपकी समस्या के लिए एल्गोरिदम अनुकूलित किया।
यह समाधान पहले से विलय वाली श्रेणियों की मौजूदा सूची में एक नई आईपी रेंज जोड़ने की अनुमति देता है (जबकि अन्य समाधान सूची-से-रेंज-टू-मर्ज सॉर्ट किए जाने पर भरोसा करते हैं और पहले से ही विलय करने के लिए एक नई श्रेणी जोड़ने की अनुमति नहीं देते हैं रेंज सूची)। यह add_range समारोह में bisect मॉड्यूल का उपयोग कर जगह है जहाँ नया आईपी रेंज सम्मिलित करने के लिए खोजने के लिए और फिर अनावश्यक आईपी अंतराल को हटाने और समायोजित सीमाओं के साथ नई रेंज डालने ताकि नई रेंज हटाए गए सभी सीमाओं को गले लगाती है के द्वारा किया जाता है।
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']
यह मैं कोड करने के लिए बहुत मज़ा था! कि के लिए धन्यवाद :)
छंटाई और फिर मेरे लिए एक बहुत अच्छा समाधान की तरह मजबूत बनाने लगता है जाने के लिए शायद बेहतर तरीका है। ओ (NLG (एन))। सुनिश्चित नहीं है कि यह बेहतर किया जा सकता है। –
@ColinD मुझे यकीन है कि वह श्रेणियों से लेकर – agf