Number set type

Discussion in 'Python' started by Heiko Wundram, Dec 29, 2005.

  1. Hi all!

    I'm wondering whether there is some form of number set type implemented in
    pure Python. I'm currently in the process of implementing one myself (for
    an IPv4 address range type), and if there's some form of reference
    implementation I'd love to see it. I've not found a reasonably complete
    implementation anywhere so far.

    To explain what I mean with number set: a set type that doesn't store
    individual entries but as it only contains numbers can store ranges of
    numbers.

    Basically what it boils down to is implementing intersection reasonably
    fast, because all other set operations can be reduced to intersection and
    union (which is easy to implement). I have implementations for both, but
    only union is fast with O(n), intersection is currently O(n^2).

    But, anyway, if anybody knows of some implementation I can have a look at,
    please let me know.

    Thanks!

    --- Heiko.
     
    Heiko Wundram, Dec 29, 2005
    #1
    1. Advertising

  2. Heiko Wundram

    Justin Azoff Guest

    You could use IPy...
    http://svn.23.nu/svn/repos/IPy/trunk/IPy.py is one location for it...

    I wonder where you get O(n) and O(n^2) from... CIDR blocks are all
    sequential.. All you need to store is the starting and ending address
    or length. Then any set operation only has to deal with 4 numbers, and
    should be literally a few lines of code with no loops.
     
    Justin Azoff, Dec 29, 2005
    #2
    1. Advertising

  3. Justin Azoff wrote:
    > You could use IPy...
    > http://svn.23.nu/svn/repos/IPy/trunk/IPy.py is one location for it...


    I know about IPy... But: it simply doesn't implement all I need it for.

    > I wonder where you get O(n) and O(n^2) from... CIDR blocks are all
    > sequential.. All you need to store is the starting and ending address
    > or length. Then any set operation only has to deal with 4 numbers, and
    > should be literally a few lines of code with no loops.


    You make assumptions that my usage simply doesn't fill. An IP4Range must
    consist of more than a single block of IP addresses (like 192.168.0.0/24
    _and_ 192.168.10.0/24), that's why it's an IP4Range and not a IP4Network
    (which I implement as an addr/mask pair in my IP4 abstraction).

    An IP4Range can consist of several different ranges (which are of course
    normalized and disjunct). I can specify what I meant by O(n) and O(n^2):

    Union of two IP4Ranges is simply normalizing a concatenated list of both
    IP4Range ranges. Normalizing takes O(log n)+O(n) = O(n) steps, where n is
    the number of ranges in the combined IP4Range.

    Intersection takes O(n^2) steps in my current implementation (which I know
    is mathematically correct), where n is max(n_1,n_2) where n_1 is the number
    of ranges in the first IP4Range and n_2 the number of ranges in the second
    IP4Range respectively.

    Intersecting two IP4Ranges can be done with fewer steps, and I think it
    could be done in O(n) in the case of normalized and sorted ranges, and I
    have a few ideas of myself, but I'm currently too lazy to try to prove them
    correct.

    Just as intersection and union can be done more efficiently, I guess that
    several set operations can be done the simple way (like
    self.difference(other) <=> self.union(other.inverse()), whereby inverse is
    O(n) too), but still maybe there are better algorithms to do it directly.

    Anyway, that's why I wanted to have a look at a ready implementation of a
    number set type so that I might get a glimpse at somebody elses
    implementation.

    --- Heiko.
     
    Heiko Wundram, Dec 29, 2005
    #3
  4. Correction:

    Heiko Wundram wrote:
    > You make assumptions that my usage simply doesn't fill. An IP4Range must


    be able to

    > consist of more than a single block of IP addresses (like 192.168.0.0/24
    > _and_ 192.168.10.0/24), that's why it's an IP4Range and not a IP4Network
    > (which I implement as an addr/mask pair in my IP4 abstraction).


    --- Heiko.
     
    Heiko Wundram, Dec 29, 2005
    #4
  5. Heiko Wundram

    Justin Azoff Guest

    Heiko Wundram wrote:
    > Union of two IP4Ranges is simply normalizing a concatenated list of both
    > IP4Range ranges. Normalizing takes O(log n)+O(n) = O(n) steps, where n is
    > the number of ranges in the combined IP4Range.


    I see now :) If the ranges are sorted, I bet you could just iterate
    through both at the same time, merging intersecting ranges where
    possible.

    > Intersection takes O(n^2) steps in my current implementation (which I know
    > is mathematically correct), where n is max(n_1,n_2) where n_1 is the number
    > of ranges in the first IP4Range and n_2 the number of ranges in the second
    > IP4Range respectively.
    >
    > Intersecting two IP4Ranges can be done with fewer steps, and I think it
    > could be done in O(n) in the case of normalized and sorted ranges, and I
    > have a few ideas of myself, but I'm currently too lazy to try to prove them
    > correct.


    Yes.. if they are sorted, something like this should work:

    def intersection(self, other):
    ret = []
    ai=iter(self.ranges)
    bi=iter(other.ranges)
    try :
    a = ai.next()
    b = bi.next()
    except StopIteration:
    return IP4Range([])

    while 1:
    try :
    if a.intersects(b):
    ret.append(a.intersection(b))
    a = ai.next()
    b = bi.next()
    elif a.start < b.start:
    a = ai.next()
    else :
    b = bi.next()
    except StopIteration:
    break
    return IP4Range(ret)


    --
    - Justin
     
    Justin Azoff, Dec 29, 2005
    #5
  6. Heiko Wundram

    Justin Azoff Guest

    Justin Azoff wrote:
    > Yes.. if they are sorted, something like this should work:

    Oops, that was almost right, but it would skip some ranges.

    This should always work:

    ....
    while 1:
    try :
    if a.intersects(b):
    ret.append(a.intersection(b))
    if a.end < b.end:
    a = ai.next()
    else :
    b = bi.next()
    elif a.start < b.start:
    a = ai.next()
    else :
    b = bi.next()
    except StopIteration:
    break
    return RangeList(ret)



    --
    - Justin
     
    Justin Azoff, Dec 29, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Harald Kirsch
    Replies:
    4
    Views:
    2,861
    Harald Kirsch
    Aug 31, 2004
  2. heyo
    Replies:
    3
    Views:
    939
    Dan Pop
    Apr 1, 2004
  3. pete
    Replies:
    4
    Views:
    809
    Dan Pop
    Apr 2, 2004
  4. Mack

    Count number of bits set in a number

    Mack, Sep 27, 2007, in forum: C Programming
    Replies:
    12
    Views:
    823
    Mark Bluemel
    Sep 28, 2007
  5. J.Cottingim

    set Bad variable type - SNMP::Util set

    J.Cottingim, Jul 3, 2007, in forum: Perl Misc
    Replies:
    0
    Views:
    110
    J.Cottingim
    Jul 3, 2007
Loading...

Share This Page