IPのリストは範囲

Question

は私が持っていると仮定し、Pythonでの範囲に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-esqueアルゴリズムの提案はありますか？

Answer 1

ここモジュールとして、私のバージョンです。私のアルゴリズムは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'] 

Answer 2

一度同じ問題に直面しました。唯一の違いは、効率的に線分をリストに収めなければならないということでした。それはモンテカルロシミュレーションのためのものでした。新しくランダムに生成された線分を、既存のソートされた線分とマージされた線分に追加する必要がありました。

私はあなたの問題に答えを使って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'] 

---

これは私がコーディングするために多くの楽しみでした！ありがとうございます:)

Answer 3

ipsのユニファイドフォーマットは、範囲を1組の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 

一般的な考え方は次です：私たちは別の上にレンジ1を入れた後（temp_ranges辞書に）、我々は見つけることが私が行うには、既存の効率的なアルゴリズムの多くは私の素朴な試みの下に、ということがあると信じて元の範囲の始まりと終わりを数えるだけで新しい構成された範囲。いったん平等が得られると、私たちは統一された範囲を見つけました。

Answer 4

範囲を数値のペアに変換します。これらの関数は、個々の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に戻って変換し、その後、数として各範囲のエッジをマージ/ソートすることができます。 merging time rangesに関するこの質問には素晴らしいアルゴリズムがあります。

---

1. 数字のペアに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) 
   

2. 単純な数値比較を使用して重複範囲をマージします。

3. 変換バック文字列表現に（まだ後者の形式を想定）：

   first, second = pair 
   first = long2ip(first) + '-' + long2ip(second).rsplit('.', 1)[1] 
   

Answer 5

は、ソケット/構造体を使用すると、おそらく

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)