Issue #23266: Much faster implementation of ipaddress.collapse_addresses() when there are many non-consecutive addresses.

3 files changed, 15 insertions, 7 deletions

diff --git a/Lib/ipaddress.py b/Lib/ipaddress.py
index b32a7e1..8d369e3 100644
--- a/Lib/ipaddress.py
+++ b/Lib/ipaddress.py
@@ -170,16 +170,19 @@ def _find_address_range(addresses):
         addresses: a list of IPv#Address objects.
 
     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 number of distinct IP addresses in the sequence.
 
     """
     first = last = addresses[0]
+    i = 1
     for ip in addresses[1:]:
         if ip._ip == last._ip + 1:
             last = ip
+            i += 1
         else:
             break
-    return (first, last)
+    return (first, last, i)
 
 
 def _count_righthand_zero_bits(number, bits):
@@ -346,12 +349,13 @@ def collapse_addresses(addresses):
                                  ip, nets[-1]))
             nets.append(ip)
 
-    # sort and dedup
-    ips = sorted(set(ips))
+    # sort
+    ips = sorted(ips)
 
+    # find consecutive address ranges in the sorted sequence and summarize them
     while i < len(ips):
-        (first, last) = _find_address_range(ips[i:])
-        i = ips.index(last) + 1
+        (first, last, items) = _find_address_range(ips[i:])
+        i = items + i
         addrs.extend(summarize_address_range(first, last))
 
     return _collapse_addresses_internal(addrs + nets)
diff --git a/Lib/test/test_ipaddress.py b/Lib/test/test_ipaddress.py
index c45e142..1fbd2d5 100644
--- a/Lib/test/test_ipaddress.py
+++ b/Lib/test/test_ipaddress.py
@@ -766,10 +766,11 @@ class IpaddrUnitTest(unittest.TestCase):
                           2 ** ipaddress.IPV6LENGTH)
 
     def testInternals(self):
-        first, last = ipaddress._find_address_range([
+        first, last, nitems = ipaddress._find_address_range([
             ipaddress.IPv4Address('10.10.10.10'),
             ipaddress.IPv4Address('10.10.10.12')])
         self.assertEqual(first, last)
+        self.assertEqual(nitems, 1)
         self.assertEqual(128, ipaddress._count_righthand_zero_bits(0, 128))
         self.assertEqual("IPv4Network('1.2.3.0/24')", repr(self.ipv4_network))
 
diff --git a/Misc/NEWS b/Misc/NEWS
index 1c1bbb0..c3b84eb 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -203,6 +203,9 @@ Core and Builtins
 Library
 -------
 
+- Issue #23266: Much faster implementation of ipaddress.collapse_addresses()
+  when there are many non-consecutive addresses.
+
 - Issue #23098: 64-bit dev_t is now supported in the os module.
 
 - Issue #21817: When an exception is raised in a task submitted to a