Created
January 20, 2011 21:18
-
-
Save eykd/788698 to your computer and use it in GitHub Desktop.
Profiling the factorial implementations at http://metaleks.net/programming/the-evolution-of-a-python-programmer/comment-page-1 with results for factorial(10) run 100,000 times.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # -*- coding: utf-8 -*- | |
| """Profiling The Evolution of the Python Programmer | |
| Based on the code offered in good humor at | |
| <http://metaleks.net/programming/the-evolution-of-a-python-programmer>. | |
| I thought it would be fun to profile the various approaches to a | |
| factorial implementation offered by Aleks. My attempt below. | |
| I couldn't profile the EXPERT PROGRAMMERS or the Unix Programmer, as I | |
| am missing their external implementations. ;) | |
| According to my results, the first-year Pascal student wins by a thin | |
| margin over the first-year C student. | |
| """ | |
| import sys | |
| import hotshot | |
| import hotshot, hotshot.stats | |
| from cStringIO import StringIO | |
| to_profile = [] | |
| profile_times = 100000 | |
| def profile(func): | |
| buffer = StringIO() | |
| def profile_func(): | |
| stdout = sys.stdout | |
| stderr = sys.stderr | |
| sys.stdout = buffer | |
| sys.stderr = buffer | |
| for x in xrange(profile_times): | |
| func() | |
| sys.stdout = stdout | |
| sys.stderr = stderr | |
| to_profile.append((func.__name__, profile_func)) | |
| return func | |
| n = 10 | |
| def tailcall(g): | |
| ''' | |
| Version of tail_recursion decorator using stack-frame inspection. | |
| from: | |
| http://code.activestate.com/recipes/496691-new-tail-recursion-decorator/ | |
| ''' | |
| loc_vars ={"in_loop":False,"cnt":0} | |
| def result(*args, **kwd): | |
| if not loc_vars["in_loop"]: | |
| loc_vars["in_loop"] = True | |
| while 1: | |
| tc = g(*args,**kwd) | |
| try: | |
| qual, args, kwd = tc | |
| if qual == 'continue': | |
| continue | |
| except TypeError: | |
| loc_vars["in_loop"] = False | |
| return tc | |
| else: | |
| f = sys._getframe() | |
| if f.f_back and f.f_back.f_back and \ | |
| f.f_back.f_back.f_code == f.f_code: | |
| return ('continue',args, kwd) | |
| return g(*args,**kwd) | |
| return result | |
| @profile | |
| def newbie(): | |
| def factorial(x): | |
| if x == 0: | |
| return 1 | |
| else: | |
| return x * factorial(x - 1) | |
| print factorial(n) | |
| @profile | |
| def first_year_pascal(): | |
| def factorial(x): | |
| result = 1 | |
| i = 2 | |
| while i <= x: | |
| result = result * i | |
| i = i + 1 | |
| return result | |
| print factorial(n) | |
| @profile | |
| def first_year_c(): | |
| def fact(x): #{ | |
| result = i = 1; | |
| while (i <= x): #{ | |
| result *= i; | |
| i += 1; | |
| #} | |
| return result; | |
| #} | |
| print(fact(n)) | |
| @profile | |
| def first_year_sicp(): | |
| @tailcall | |
| def fact(x, acc=1): | |
| if (x > 1): return (fact((x - 1), (acc * x))) | |
| else: return acc | |
| print(fact(n)) | |
| @profile | |
| def first_year_python(): | |
| def Factorial(x): | |
| res = 1 | |
| for i in xrange(2, x + 1): | |
| res *= i | |
| return res | |
| print Factorial(n) | |
| @profile | |
| def lazy_python_programmer(): | |
| def fact(x): | |
| return x > 1 and x * fact(x - 1) or 1 | |
| print fact(n) | |
| @profile | |
| def lazier_python_programmer(): | |
| def fact(x): | |
| return x > 1 and x * fact(x - 1) or 1 | |
| print fact(n) | |
| @profile | |
| def python_expert_programmer(): | |
| fact = lambda x: reduce(int.__mul__, xrange(2, x + 1), 1) | |
| print fact(n) | |
| @profile | |
| def python_hacker(): | |
| import sys | |
| @tailcall | |
| def fact(x, acc=1): | |
| if x: return fact(x.__sub__(1), acc.__mul__(x)) | |
| return acc | |
| sys.stdout.write(str(fact(n)) + '\n') | |
| ### No c_math implementation! | |
| # @profile | |
| # def expert_programmer(): | |
| # from c_math import fact | |
| # print fact(n) | |
| ### No c_maths implementation! | |
| # @profile | |
| # def british_expert_programmer(): | |
| # from c_maths import fact | |
| # print fact(n) | |
| @profile | |
| def web_designer(): | |
| def factorial(x): | |
| #------------------------------------------------- | |
| #--- Code snippet from The Math Vault --- | |
| #--- Calculate factorial (C) Arthur Smith 1999 --- | |
| #------------------------------------------------- | |
| result = str(1) | |
| i = 1 #Thanks Adam | |
| while i <= x: | |
| #result = result * i #It's faster to use *= | |
| #result = str(result * result + i) | |
| #result = int(result *= i) #?????? | |
| result = str(int(result) * i) | |
| #result = int(str(result) * i) | |
| i = i + 1 | |
| return result | |
| print factorial(n) | |
| ### No factorial implementation! | |
| # @profile | |
| # def unix_programmer(): | |
| # import os | |
| # def fact(x): | |
| # os.system('factorial ' + str(x)) | |
| # fact(n) | |
| @profile | |
| def windows_programmer(): | |
| NULL = None | |
| def CalculateAndPrintFactorialEx(dwNumber, | |
| hOutputDevice, | |
| lpLparam, | |
| lpWparam, | |
| lpsscSecurity, | |
| *dwReserved): | |
| if lpsscSecurity != NULL: | |
| return NULL #Not implemented | |
| dwResult = dwCounter = 1 | |
| while dwCounter <= dwNumber: | |
| dwResult *= dwCounter | |
| dwCounter += 1 | |
| hOutputDevice.write(str(dwResult)) | |
| hOutputDevice.write('\n') | |
| return 1 | |
| import sys | |
| CalculateAndPrintFactorialEx(6, sys.stdout, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL) | |
| @profile | |
| def enterprise_programmer(): | |
| def new(cls, *args, **kwargs): | |
| return cls(*args, **kwargs) | |
| class Number(object): | |
| pass | |
| class IntegralNumber(int, Number): | |
| def toInt(self): | |
| return new (int, self) | |
| class InternalBase(object): | |
| def __init__(self, base): | |
| self.base = base.toInt() | |
| def getBase(self): | |
| return new (IntegralNumber, self.base) | |
| class MathematicsSystem(object): | |
| def __init__(self, ibase): | |
| Abstract | |
| @classmethod | |
| def getInstance(cls, ibase): | |
| try: | |
| cls.__instance | |
| except AttributeError: | |
| cls.__instance = new (cls, ibase) | |
| return cls.__instance | |
| class StandardMathematicsSystem(MathematicsSystem): | |
| def __init__(self, ibase): | |
| if ibase.getBase() != new (IntegralNumber, 2): | |
| raise NotImplementedError | |
| self.base = ibase.getBase() | |
| def calculateFactorial(self, target): | |
| result = new (IntegralNumber, 1) | |
| i = new (IntegralNumber, 2) | |
| while i <= target: | |
| result = result * i | |
| i = i + new (IntegralNumber, 1) | |
| return result | |
| print StandardMathematicsSystem.getInstance(new (InternalBase, new (IntegralNumber, 2))).calculateFactorial(new (IntegralNumber, 6)) | |
| if __name__ == "__main__": | |
| for name, func in to_profile: | |
| print '=' * 20, name | |
| prof = hotshot.Profile("quick_%s.prof" % name) | |
| prof.runcall(func) | |
| prof.close() | |
| stats = hotshot.stats.load("quick_%s.prof" % name) | |
| stats.strip_dirs() | |
| stats.sort_stats('time', 'calls') | |
| stats.print_stats(20) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Results run on a MacBook 2GHz Intel Core 2 Duo. | |
| ==================== newbie | |
| 1200001 function calls (200001 primitive calls) in 1.788 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 1100000/100000 0.939 0.000 0.939 0.000 python_evolution.py:98(factorial) | |
| 100000 0.760 0.000 1.699 0.000 python_evolution.py:96(newbie) | |
| 1 0.089 0.089 1.788 1.788 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== first_year_pascal | |
| 200001 function calls in 0.871 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 0.557 0.000 0.812 0.000 python_evolution.py:106(first_year_pascal) | |
| 100000 0.255 0.000 0.255 0.000 python_evolution.py:108(factorial) | |
| 1 0.059 0.059 0.871 0.871 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== first_year_c | |
| 200001 function calls in 0.875 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 0.564 0.000 0.818 0.000 python_evolution.py:118(first_year_c) | |
| 100000 0.254 0.000 0.254 0.000 python_evolution.py:120(fact) | |
| 1 0.057 0.057 0.875 0.875 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== first_year_sicp | |
| 2200001 function calls (1300001 primitive calls) in 7.496 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 1000000/100000 4.143 0.000 5.985 0.000 python_evolution.py:48(result) | |
| 1000000 1.842 0.000 3.651 0.000 python_evolution.py:132(fact) | |
| 100000 1.208 0.000 7.396 0.000 python_evolution.py:130(first_year_sicp) | |
| 100000 0.203 0.000 0.203 0.000 python_evolution.py:39(tailcall) | |
| 1 0.100 0.100 7.496 7.496 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== first_year_python | |
| 200001 function calls in 0.908 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 0.562 0.000 0.849 0.000 python_evolution.py:138(first_year_python) | |
| 100000 0.287 0.000 0.287 0.000 python_evolution.py:140(Factorial) | |
| 1 0.059 0.059 0.908 0.908 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== lazy_python_programmer | |
| 1100001 function calls (200001 primitive calls) in 1.697 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 1000000/100000 0.885 0.000 0.885 0.000 python_evolution.py:150(fact) | |
| 100000 0.719 0.000 1.604 0.000 python_evolution.py:148(lazy_python_programmer) | |
| 1 0.093 0.093 1.697 1.697 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== lazier_python_programmer | |
| 1100001 function calls (200001 primitive calls) in 1.674 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 1000000/100000 0.868 0.000 0.868 0.000 python_evolution.py:157(fact) | |
| 100000 0.716 0.000 1.584 0.000 python_evolution.py:155(lazier_python_programmer) | |
| 1 0.089 0.089 1.674 1.674 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== python_expert_programmer | |
| 200001 function calls in 1.197 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 0.583 0.000 1.132 0.000 python_evolution.py:162(python_expert_programmer) | |
| 100000 0.549 0.000 0.549 0.000 python_evolution.py:164(<lambda>) | |
| 1 0.064 0.064 1.197 1.197 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== python_hacker | |
| 2400001 function calls (1400001 primitive calls) in 8.591 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 1100000/100000 4.948 0.000 7.326 0.000 python_evolution.py:48(result) | |
| 1100000 2.378 0.000 4.537 0.000 python_evolution.py:171(fact) | |
| 100000 0.958 0.000 8.485 0.000 python_evolution.py:168(python_hacker) | |
| 100000 0.201 0.000 0.201 0.000 python_evolution.py:39(tailcall) | |
| 1 0.106 0.106 8.591 8.591 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== web_designer | |
| 200001 function calls in 4.118 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 3.397 0.000 3.397 0.000 python_evolution.py:192(factorial) | |
| 100000 0.642 0.000 4.039 0.000 python_evolution.py:190(web_designer) | |
| 1 0.079 0.079 4.118 4.118 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== windows_programmer | |
| 200001 function calls in 0.937 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 0.483 0.000 0.483 0.000 python_evolution.py:221(CalculateAndPrintFactorialEx) | |
| 100000 0.367 0.000 0.850 0.000 python_evolution.py:218(windows_programmer) | |
| 1 0.087 0.087 0.937 0.937 python_evolution.py:21(profile_func) | |
| 0 0.000 0.000 profile:0(profiler) | |
| ==================== enterprise_programmer | |
| 2800001 function calls (2400001 primitive calls) in 23.460 CPU seconds | |
| Ordered by: internal time, call count | |
| ncalls tottime percall cumtime percall filename:lineno(function) | |
| 100000 17.308 0.000 23.345 0.000 python_evolution.py:240(enterprise_programmer) | |
| 1500000/1100000 2.323 0.000 3.259 0.000 python_evolution.py:242(new) | |
| 100000 1.010 0.000 1.473 0.000 python_evolution.py:277(calculateFactorial) | |
| 100000 0.812 0.000 2.154 0.000 python_evolution.py:263(getInstance) | |
| 100000 0.376 0.000 0.983 0.000 python_evolution.py:272(__init__) | |
| 100000 0.376 0.000 0.376 0.000 python_evolution.py:259(MathematicsSystem) | |
| 200000 0.251 0.000 0.466 0.000 python_evolution.py:256(getBase) | |
| 100000 0.224 0.000 0.224 0.000 python_evolution.py:271(StandardMathematicsSystem) | |
| 100000 0.176 0.000 0.176 0.000 python_evolution.py:248(IntegralNumber) | |
| 100000 0.163 0.000 0.404 0.000 python_evolution.py:253(__init__) | |
| 100000 0.145 0.000 0.241 0.000 python_evolution.py:249(toInt) | |
| 100000 0.130 0.000 0.130 0.000 python_evolution.py:252(InternalBase) | |
| 1 0.115 0.115 23.460 23.460 python_evolution.py:21(profile_func) | |
| 100000 0.050 0.000 0.050 0.000 python_evolution.py:245(Number) | |
| 0 0.000 0.000 profile:0(profiler) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment