[issue20826] Faster implementation to collapse consecutive ip-networks

Antoine Pitrou added the comment: I've now committed this. exhuma, if you have any further observations or results, don't hesitate to post them! -- resolution: -> fixed stage: patch review -> commit review status: open -> closed ___ Python tracker

[issue20826] Faster implementation to collapse consecutive ip-networks

Roundup Robot added the comment: New changeset 8867874a2b7d by Antoine Pitrou in branch 'default': Issue #20826: Optimize ipaddress.collapse_addresses(). http://hg.python.org/cpython/rev/8867874a2b7d -- nosy: +python-dev ___ Python tracker

[issue20826] Faster implementation to collapse consecutive ip-networks

Antoine Pitrou added the comment: Updated patch, a bit faster yet. After issue16531 is committed, it is now ~15x faster than 3.4. -- Added file: http://bugs.python.org/file35233/faster_collapse2.patch ___ Python tracker

[issue20826] Faster implementation to collapse consecutive ip-networks

Antoine Pitrou added the comment: It seems like the speed of Network.supernet() is a bottleneck here. issue16531 would probably allow making supernet() much faster. -- ___ Python tracker __

[issue20826] Faster implementation to collapse consecutive ip-networks

Antoine Pitrou added the comment: Uh, those measurements are wrong, sorry, since tester.py doesn't consume the iterator. When consuming the iterator, the patch is ~ 4x faster than the original code, which is more reasonable :-) -- ___ Python tracker

[issue20826] Faster implementation to collapse consecutive ip-networks

Antoine Pitrou added the comment: Here is a much faster patch, around 30x faster than the original code. With exhuma's data set and tester.py, the original code gives: $ time python3.4 tester.py Execution time: 5.949284339199949 seconds real0m30.152s user0m30.104s sys 0m0.016s Th

[issue20826] Faster implementation to collapse consecutive ip-networks

Antoine Pitrou added the comment: >From a quick look, the algorithm is indeed correct, and it should perform >better on average than the previous one. Note: both algorithms are O(n**2) worst case, not O(n). -- nosy: +pitrou ___ Python tracker

[issue20826] Faster implementation to collapse consecutive ip-networks

Changes by Ezio Melotti : -- nosy: +ezio.melotti stage: -> patch review ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue20826] Faster implementation to collapse consecutive ip-networks

Michel Albert added the comment: Sorry for the late reply. I wanted to take some time and give a more detailed explanation. At least to the best of my abilities :) I attached a zip-file with my quick-and-dirty test-rig. The zip contains: * gendata.py -- The script I used to generate test-data

[issue20826] Faster implementation to collapse consecutive ip-networks

pmoody added the comment: Hey Exhuma, thanks for the patch. Can you give me an example list on which this shift reduce approach works much better? -- assignee: -> pmoody ___ Python tracker __

[issue20826] Faster implementation to collapse consecutive ip-networks

New submission from Michel Albert: This alternative implementation runs over the ``addresses`` collection only once, and "backtracks" only if necessary. Inspired by a "shift-reduce" approach. Technically both are O(n), so the best case is always the same. But the old implementation runs over t