Functional schmunctional...

[r0g]

I remember being forced to do a bit of functional programming in ML back
at Uni in the mid 90, the lecturers were all in a froth about it and I
must admit the code was elegant to look at. The problem was the dog slow
performance for anything half practical, especially with recursion being
the technique de jour. The HP workstations we were using were really
quite beefy for their time yet simple ML stuff would just murder the CPU
and RAM. Added to that, recursive stuff could be extremely confusing to
debug so I wrote it off as a nice idea in concept but a waste of my time
for anything practical.

So fast forward 15 years to this very afternoon... I needed a routine to
convert IP address strings to INET numbers and vice-versa and I remember
writing one a couple of years back when I first picked up Python. So I
went and dug it out. Looking back at old code can be a bit dispiriting
though and this was no exception...

def inet2ip(n):
p = (n/16777216)
q = ((n-(p*16777216))/65536)
r = ((n-((p*16777216)+(q*65536)))/256)
s = ((n-((p*16777216)+(q*65536)+(r*256))))
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

def ip2in(a):
li = a.split('.')
assert len(li) == 4
a = int(li[0])*16777216
b = int(li[1])*65536
c = int(li[2])*256
d = int(li[3])
return a+b+c+d


I thought "OMG, how naive and inelegant that looks, I can do far better
than that, after all I know things like list comprehensions and
map/reduce now!". I had also noticed over the last year or two a lot of
chatter about functional programming especially in conjunction with python.

It seems to me that procedural programming has taken quite a kicking
against the more OO and functional methodologies over the last few years
and given my nothing-but-positive experience with OO of late I was
reconsidering the strength of my old opinions on FP. Maybe it was, as my
lecturers thought, the paradigm of the future and I was being a
crotchety old stick in the mud by spurning it as slow and confusing.

With this in mind I set about applying my hard won Python knowledge and
wisdom to the rewriting of these functions, not for any particularly
practical reasons, just to see what improvements I could wreak on them
several years down the line.

The IP string to INET number was first and I decided to throw list
comprehensions at it...

def ip2inet(a):
li = a.split('.')
assert len(li) == 4 or len(li) == 6
return reduce(add,[int(li[e])*(256**((len(li)-1)-e)) for e in
xrange(0,len(li))])

Now, that did made it completely unreadable but I thought, "it's pretty
much all one line now so I've gained some conciseness and at least it
should run a little faster". After all list comprehensions are often
fast aren't they? Well actually no, It runs at less than half the speed
of the previous function and now it's entirely lexically impenetrable.

Shit :-(

So far so bad... As inauspicious as these beginnings were I figured I'd
plug on anyway and try a functional approach to the INET number to IP
string function - the above experience having reinforced in me the
notion that clarity is paramount. Functional programming is all about
the clarity and elegance right?

I figured it might be worth trading a few cycles for at least,
especially as the machine I'm using here in 2009 has more RAM and CPU
grunt than whole Uni computer department did back in 1994. Not only that
I would only need to do 4 or 6 recursions in this algorithm and so I
shouldn't need to worry about the exponential inefficiency problems of
yore...

def inet2ip(n, l=[], c=4):
if c==0: return ".".join(l)
p = 256**( c-1 )
l.append( str(n/p) )
return inet2ip( n-(n/p)*p, l, c-1 )

The thing is, that's not really any clearer though is it? I'd wager if
you didn't know already it would take you longer to figure out this
version than it would the original. Still, "at least" I thought "it's
more concise than the last one and it scales to IPv6 far more
elegantly". I figured as long as the performance wasn't too lousy I
would keep it and so I quickly ran a little benchmark to see how much of
a performance hit I would be taking by doing so. The results for 10000
iterations of each were as follows...

0.113744974136 seconds for old INET->IP method
27.7441999912 seconds for new INET->IP method

:-/

FFS!

It just goes to show that...

1) Thinking you're a smart arse and actually being a smart arse are two
quite different things.

2) You should always take received wisdom with a good pinch of salt.

3) People aren't exaggerating when they say Python function calls are
expensive are they!


Roger Heathcote.

 

[Paul Rubin]

def inet2ip(n):
p = (n/16777216)
q = ((n-(p*16777216))/65536)
r = ((n-((p*16777216)+(q*65536)))/256)
s = ((n-((p*16777216)+(q*65536)+(r*256))))
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

from struct import pack
def inet2ip(n):
xs = pack('L',n)
return '.'.join(str(ord(x)) for x in xs)

 

[bearophileHUGS]

Here a small benchmark:

def ip2inet01(a): # can't be used with 6
li = a.split('.')
assert len(li) == 4
a = int(li[0])*16777216
b = int(li[1])*65536
c = int(li[2])*256
d = int(li[3])
return a+b+c+d

from itertools import count

def ip2inet02(a):
blocks = a.split('.')
assert len(blocks) in (4, 6)
return sum(map(lambda (i, n): int(i) * 256**n, zip(reversed
(blocks), count(0))))

def ip2inet03(iptxt):
bytes = map(int, iptxt.strip().split("."))[::-1]
assert len(bytes) in (4, 6)
return sum(by * 256**po for po, by in enumerate(bytes))

def ip2inet04(iptxt):
bytes = map(int, reversed(iptxt.strip().split(".")))
assert len(bytes) in (4, 6)
powers256 = [1, 256, 65536, 16777216, 4294967296, 1099511627776]
return sum(by * powers256[po] for po, by in enumerate(bytes))

def ip2inet05(iptxt):
bytes = (int(by) for by in reversed(iptxt.strip().split(".")))
parts = [by * ip2inet05.powers256[po] for po, by in enumerate
(bytes)]
assert len(parts) in (4, 6)
return sum(parts)
ip2inet05.powers256 = [1, 256, 65536, 16777216, 4294967296,
1099511627776]

def ip2inet06(a):
li = a.split('.')
n = len(li)
assert n == 4 or n == 6
if n == 4:
return (int(li[0]) * 16777216 +
int(li[1]) * 65536 +
int(li[2]) * 256 +
int(li[3]))
else:
return (int(li[0]) * 1099511627776 +
int(li[1]) * 4294967296 +
int(li[2]) * 16777216 +
int(li[3]) * 65536 +
int(li[4]) * 256 +
int(li[5]))

def ip2inet07(iptxt):
bytes = map(int, iptxt.strip().split("."))[::-1]
assert len(bytes) in (4, 6)
return sum(by * ip2inet07.pows[po] for po, by in enumerate(bytes))
ip2inet07.pows = [1, 256, 65536, 16777216, 4294967296, 1099511627776]

from struct import pack
def ip2inet08(n): # error
xs = pack('L', n)
return '.'.join(str(ord(x)) for x in xs)

def ip2inet09(iptxt): # short and readable
bytes = map(int, iptxt.strip().split("."))[::-1]
assert len(bytes) in (4, 6)
return sum(by << (8*po) for po, by in enumerate(bytes))

def ip2inet10(iptxt):
count = 0
result = 0
for byte in iptxt.strip().split("."):
result <<= 8
result += int(byte)
count += 1
assert count in (4, 6)
return result

def ip2inet11(iptxt):
bytes = iptxt.strip().split(".")
assert len(bytes) in (4, 6)
result = 0
for byte in bytes:
result <<= 8
result += int(byte)
return result

def ip2inet12(iptxt):
bytes = iptxt.strip().split(".")
assert len(bytes) in (4, 6)
result = 0
for byte in bytes:
result = (result << 8) + int(byte)
return result

def ip2inet13(a): # fastest and readable
li = a.split('.')
n = len(li)
assert n == 4 or n == 6
if n == 4:
return ((int(li[0]) << 24) +
(int(li[1]) << 16) +
(int(li[2]) << 8) +
int(li[3]))
else:
return ((int(li[0]) << 40) +
(int(li[1]) << 32) +
(int(li[2]) << 24) +
(int(li[3]) << 16) +
(int(li[4]) << 8) +
int(li[5]))



def main():
from timeit import default_timer as clock

ip4 = "155.16.187.87"
ip6 = "7.155.16.187.87.255"
algos = [ip2inet02, ip2inet03, ip2inet04, ip2inet05, ip2inet06,
ip2inet07, ip2inet09, ip2inet10, ip2inet11, ip2inet12,
ip2inet13]
for algo in algos:
assert algo(ip4) == 2601565015 and algo(ip6) == 8362582038527
t0 = clock()
for i in xrange(10000):
algo(ip4)
algo(ip6)
print algo.__name__, round(clock() - t0, 2), "s"

import psyco; psyco.full()
print "With Psyco:"
for algo in algos:
t0 = clock()
for i in xrange(10000):
algo(ip4)
algo(ip6)
print algo.__name__, round(clock() - t0, 2), "s"


main()

ip2inet02 2.68 s
ip2inet03 1.79 s
ip2inet04 1.72 s
ip2inet05 1.88 s
ip2inet06 0.98 s
ip2inet07 1.57 s
ip2inet09 1.5 s
ip2inet10 1.07 s
ip2inet11 1.07 s
ip2inet12 1.03 s
ip2inet13 0.95 s

With Psyco (indipendent run! Not normally successive):
ip2inet02 2.66 s
ip2inet03 1.66 s
ip2inet04 1.97 s
ip2inet05 1.66 s
ip2inet06 0.57 s
ip2inet07 1.5 s
ip2inet09 1.54 s
ip2inet10 0.53 s
ip2inet11 0.76 s
ip2inet12 0.52 s
ip2inet13 0.8 s

So if you need speed you the version #13 is better, if you want short
and readable code (but not too much slow) you can use #9, and if you
want code easy to understand by every one and easy to translate to
other languages then you can use #12.

Bye,
bearophile

 

[Terry Reedy]

def inet2ip(n):
p = (n/16777216)
q = ((n-(p*16777216))/65536)
r = ((n-((p*16777216)+(q*65536)))/256)
s = ((n-((p*16777216)+(q*65536)+(r*256))))
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

Beyond what other wrote:
To future-proof code, use // instead of / for integer division.
To get both quotient and remainder, use divmod(num,den)
For future reading (and generalization) documenting magic constants helps.

In 3.0:

def inet2ip(n):
p = (n//16777216)
q = ((n-(p*16777216))//65536)
r = ((n-((p*16777216)+(q*65536)))//256)
s = ((n-((p*16777216)+(q*65536)+(r*256))))
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

def inet2ip2(n):
p,n=divmod(n,16777216) # 1<<24
q,n=divmod(n,65536) # 1<<16
r,s=divmod(n,256) # 1<<8
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

print(inet2ip(1000000000), inet2ip2(1000000000))
59.154.202.0 59.154.202.0

 

[r0g]

Here a small benchmark:

def ip2inet01(a): # can't be used with 6
li = a.split('.')

<snip>

Wow, thanks everybody for all the suggestions, v.interesting esp as I
didn't even ask for any suggestions! This is a fantastically didactic
newsgroup: you start off just musing about functional programming, you
end up learning python has a rich set of augmented assignment operators,
brilliant


Roger Heathcote.

 

[python]

This is a fantastically didactic newsgroup: you start off just musing about <fill-in-the-blank>, you end up learning python has <some great feature>, brilliant

+1 !!

Malcolm

 

[Steve Holden]

Beyond what other wrote:
To future-proof code, use // instead of / for integer division.
To get both quotient and remainder, use divmod(num,den)
For future reading (and generalization) documenting magic constants helps.

In 3.0:

def inet2ip(n):
p = (n//16777216)
q = ((n-(p*16777216))//65536)
r = ((n-((p*16777216)+(q*65536)))//256)
s = ((n-((p*16777216)+(q*65536)+(r*256))))
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

def inet2ip2(n):
p,n=divmod(n,16777216) # 1<<24
q,n=divmod(n,65536) # 1<<16
r,s=divmod(n,256) # 1<<8
return str(p)+"."+str(q)+"."+str(r)+"."+str(s)

print(inet2ip(1000000000), inet2ip2(1000000000))

59.154.202.0 59.154.202.0

Jeez, doesn't anyone read the fine manual any more? I hope this was just
an academic exercise.

Holden's rule: when it looks simple enough to be worth including in the
standard library it may well already *be* in the standard library.

regards
Steve

 

[Michele Simionato]

def ip2inet(a):
  li = a.split('.')
  assert len(li) == 4 or len(li) == 6
  return reduce(add,[int(li[e])*(256**((len(li)-1)-e)) for e in
xrange(0,len(li))])

Aagh! Notice that functional programming is not about filter, map,
reduce and other unreadable constructs: it is much more about avoiding
mutation.

Your problem has been already solved by using the standard library;
however, if you want to know more about functional programming, I
could as well advertise my own series of "Adventures of a Pythonista
in Schemeland" which is facing exactly that topic right now:

http://www.artima.com/weblogs/viewpost.jsp?thread=248953

 

[wolfram.hinderer]

def inet2ip(n, l=[], c=4):
  if c==0: return ".".join(l)
  p = 256**( c-1 )
  l.append( str(n/p) )
  return inet2ip( n-(n/p)*p, l, c-1 )

The results for 10000
iterations of each were as follows...

0.113744974136 seconds for old INET->IP method
27.7441999912 seconds for new INET->IP method

:-/

That's probably because your new function is broken:

def inet2ip(n, l=[], c=4):

if c==0: return ".".join(l)
p = 256**( c-1 )
l.append( str(n/p) )
return inet2ip( n-(n/p)*p, l, c-1 )
'0.0.0.0.0.0.0.0.0.0.0.0'

 

[Hendrik van Rooyen]

Jeez, doesn't anyone read the fine manual any more? I hope this was just
an academic exercise.


Holden's rule: when it looks simple enough to be worth including in the
standard library it may well already *be* in the standard library.

Aaah! But how do you find it, if you don't already know
where it lives and what it's called ?

- Hendrik

 

[Steve Holden]

Aaah! But how do you find it, if you don't already know
where it lives and what it's called ?

Well, my usual answer would be "Ask on c.l.py", but it appears that's no
longer reliable. Jeez, doesn't anyone ... (rinse and repeat).

regards
Steve