Friday 9 February 2007

Sorting IP addresses in python

Here's a quick example of a function to sort a list of IP addresses in python using the decorate-sort-undecorate idiom (aka Schwartzian Transform) and the IPy module.
def sort_ip_list(ip_list):
"""Sort an IP address list."""
from IPy import IP
ipl = [(IP(ip).int(), ip) for ip in ip_list]
ipl.sort()
return [ip[1] for ip in ipl]

And here is an example of it in use:
>>> l = ['127.0.0.1', '192.168.0.10', '192.168.0.1', '10.1.1.1', '172.16.255.254']
>>> sort_ip_list(l)
['10.1.1.1', '127.0.0.1', '172.16.255.254', '192.168.0.1', '192.168.0.10']

5 comments:

Rick Copeland said...

Another neat trick is to use the "key" argument in the sort/sorted functions. Since Python 2.4(ish) you have also been able to do the following:

def sort_ip_list(ip_list):
  from IPy import IP
  return sorted(ip_list,
    key=lambda ip:IP(ip).int())

The keys are calculated only once, so you don't incur the penalty of the old sort-with-custom-compare-function method.

Matthew Flanagan said...

Thanks Rick,

I was curious so I did a quick benchmark on them and your method is only about 1% faster. Below is the code I used. Let me know if there are any flaws in my methodology.

$ ./ipsorttest.py
schwartzian 468.488626003 seconds
key 463.980193138 seconds


#!/usr/local/bin/python

IP_LIST = (
 '192.168.1.1',
 '192.168.1.2',
 '10.168.1.24',
 '192.168.1.6',
 '192.168.1.7',
 '192.168.1.20',
 '192.168.1.21',
 '10.168.1.1',
 '192.168.1.24',
 '10.168.1.2',
 '192.168.1.4',
 '10.168.1.4',
 '10.168.1.5',
 '192.168.1.23',
 '10.168.1.6',
 '10.168.1.7',
 '10.168.1.20',
 '10.168.1.21',
 '192.168.1.5',
 '10.168.1.23'
)

def sort_ip_list(ip_list):
 from IPy import IP
 ipl = [(IP(ip).int(), ip) for ip in ip_list]
 ipl.sort()
 return [ip[1] for ip in ipl]

def sort_ip_list2(ip_list):
 from IPy import IP
 return sorted(ip_list, key=lambda ip:IP(ip).int())


if __name__ == '__main__':
 from timeit import Timer
 t1 = Timer('sort_ip_list(IP_LIST)', 'from __main__ import sort_ip_list, IP_LIST').timeit()
 print "schwartzian %s seconds" % t1
 t2 = Timer('sort_ip_list2(IP_LIST)', 'from __main__ import sort_ip_list2, IP_LIST').timeit()
 print "key %s seconds" % t2

Jason Rahm said...

What if you want to to sort by IP but the IP's are values in a list of dictionaries? Ex:

l = [{'destination': '192.168.0.0', 'netmask': '255.255.255.0' }, {'destination': '0.0.0.0', 'netmask': '0.0.0.0' }]

Matthew Flanagan said...

@Jason: Something like this should work:

def sort_ip_dicts(ip_dicts):
from IPy import IP
ipl = [(IP(i['destination']).int(), i) for i in ip_dicts]
ipl.sort()
return [ip[1] for ip in ipl]

Jason Rahm said...

Yep, that was it. Thanks so much!