Mainly Tech projects on Python and Electronic Design Automation.

Sunday, May 27, 2012

Python: Choice of the one obvious way to do it.

I just worked on a new Rosetta Code task on Fibonacci-like sequences where the solution works by giving the initial conditions and being returned something that can then create members of the defined series. You create a series generator factory then use the series generator returned. (The above uses the word generator in its non programming specific sense).

Currently we have three versions of answers to the task in Python:




Python: function returning a function

>>> def fiblike(start):
 addnum = len(start)
 memo = start[:]
 def fibber(n):
  try:
   return memo[n]
  except IndexError:
   ans = sum(fibber(i) for i in range(n-addnum, n))
   memo.append(ans)
   return ans
 return fibber
 
>>> fibo = fiblike([1,1])
>>> [fibo(i) for i in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> lucas = fiblike([2,1])
>>> [lucas(i) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
>>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) :
 fibber = fiblike([1] + [2**i for i in range(n-1)])
 print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
 
 
n= 2,  fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6,  hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8,  octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9,  nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10,  decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> 


Python: Callable class

>>> class Fiblike():
 def __init__(self, start):
  self.addnum = len(start)
  self.memo = start[:]
 def __call__(self, n):
  try:
   return self.memo[n]
  except IndexError:
   ans = sum(self(i) for i in range(n-self.addnum, n))
   self.memo.append(ans)
   return ans
 
 
>>> fibo = Fiblike([1,1])
>>> [fibo(i) for i in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> lucas = Fiblike([2,1])
>>> [lucas(i) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
>>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) :
 fibber = Fiblike([1] + [2**i for i in range(n-1)])
 print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
 
 
n= 2,  fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6,  hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8,  octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9,  nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10,  decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> 


Generator

from itertools import islice, cycle
 
def fiblike(tail):
    for x in tail:
        yield x
    for i in cycle(xrange(len(tail))):
        tail[i] = x = sum(tail)
        yield x
 
fibo = fiblike([1, 1])
print list(islice(fibo, 10))
lucas = fiblike([2, 1])
print list(islice(lucas, 10))
 
suffixes = "fibo tribo tetra penta hexa hepta octo nona deca"
for n, name in zip(xrange(2, 11), suffixes.split()):
    fib = fiblike([1] + [2 ** i for i in xrange(n - 1)])
    items = list(islice(fib, 15))
    print "n=%2i, %5snacci -> %s ..." % (n, name, items)
Output:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
n= 2,  fibonacci -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] ...
n= 3, tribonacci -> [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136] ...
n= 4, tetranacci -> [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536] ...
n= 5, pentanacci -> [1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930] ...
n= 6,  hexanacci -> [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617] ...
n= 7, heptanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936] ...
n= 8,  octonacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080] ...
n= 9,  nonanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144] ...
n=10,  decanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172] ...


Three answers and Zen

So how does the existence of three ways of giving an answer square with that part of the Zen of Python which states:
    There should be one-- and preferably only one --obvious way to do it.

This comes down to a matter of style. Python supports many programming styles, (often called programming paradigms). What example might best fit a situation should depend on the surrounding programming style in use. The function calling a function, callable class, and generator solutions might best fit situations where it is to fit within programs using the procedural, object-oriented and functional styles respectively.

3 comments:

  1. Which one is easier to instrument? I'd go with that one.

    ReplyDelete
  2. generator is not equivalent to innner function. I'm sure you know that. And classes approach is just unpythonic. See video "Stop writing classes". And of course, you should just use functools.lru_cache instead of rolling your own memoization.

    ReplyDelete
    Replies
    1. Glad to see you know the rules. You might be better off rigidly following them. As you stated.

      Delete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive