From 241077dc2bc5f5f9c6293eaaa52823a58ec76a6b Mon Sep 17 00:00:00 2001 From: Alex Finkel Date: Fri, 31 Jul 2015 14:56:10 -0700 Subject: Performance fix for collapse_addr_list. Calling "ips.index(last)" inside a loop over all ips does O(n) linear searches, leading to quadratic performance. The index call isn't necessary; the position of 'last' in ips can be inferred if _find_address_range returns the position that it found 'last' at. --- trunk/ipaddr.py | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/trunk/ipaddr.py b/trunk/ipaddr.py index 33eb405..c30f298 100644 --- a/trunk/ipaddr.py +++ b/trunk/ipaddr.py @@ -156,16 +156,19 @@ def _find_address_range(addresses): addresses: a list of IPv4 or IPv6 addresses. Returns: - A tuple containing the first and last IP addresses in the sequence. + A tuple containing the first and last IP addresses in the sequence, + and the index of the last IP address in the sequence. """ first = last = addresses[0] + last_index = 0 for ip in addresses[1:]: if ip._ip == last._ip + 1: last = ip + last_index += 1 else: break - return (first, last) + return (first, last, last_index) def _get_prefix_length(number1, number2, bits): """Get the number of leading bits that are same for two numbers. @@ -358,8 +361,8 @@ def collapse_address_list(addresses): nets = sorted(set(nets)) while i < len(ips): - (first, last) = _find_address_range(ips[i:]) - i = ips.index(last) + 1 + (first, last, last_index) = _find_address_range(ips[i:]) + i += last_index + 1 addrs.extend(summarize_address_range(first, last)) return _collapse_address_list_recursive(sorted( -- cgit v1.2.1