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
--
http://mail.python.org/mailman/listinfo/python-list
