tag:blogger.com,1999:blog-8688058551295946514.post4032040910235381597..comments2023-05-21T07:33:43.212-07:00Comments on Daily rant: Running fast code in PythonFiloxhttp://www.blogger.com/profile/07052058313681392060noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-8688058551295946514.post-54104912835988235392008-01-25T07:33:00.000-08:002008-01-25T07:33:00.000-08:00I assume the compiled Haskell program runs stand-a...I assume the compiled Haskell program runs stand-alone? To be fair in the size comparison, you should either compile the Python program to a stand-alone executable or count the shared Python installation as part of the "compiled size". On my Ubuntu system that alone takes around 10 megabytes.akaiholahttps://www.blogger.com/profile/15705799059863673635noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-36562785194514820112007-12-13T02:28:00.000-08:002007-12-13T02:28:00.000-08:00Thanks for clearing that up. I did come in a bit ...Thanks for clearing that up. I did come in a bit late and the perspective that I saw was how "fast" these times were. The article looks interesting. One thing I noticed when I ran your algorithm with n quite large was that it very quickly took all the memory in my system, but then hardly used any CPU. So it isn't even processor time where Python bogs down. It must be in keeping track and allocating space for the recursive calls like you said.Bobberinohttps://www.blogger.com/profile/16370024028686171523noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-8084712966825776292007-12-12T23:22:00.000-08:002007-12-12T23:22:00.000-08:00Ok, I see that my last post made a lot of confusio...Ok, I see that my last post made a lot of confusion. I will try to clarify things a bit. So, the recursive fibonacci algorithm (the one I used) has an exponential time complexity. For a nice explanation on why is this so, see http://www.site.uottawa.ca/~ivan/tr-educ.pdf<BR/>So, why would I use something so slow when there are clearly better (faster) algorithms? The whole point of this and one of my previous posts was not to show off different algorithms for computing the fibonacci numbers (there is a well-known formula to compute the nth number in the sequence directyl, without having to compute the first n-1 numbers), but to see how different languages handle these intensive recursive calls. As you could read in my posts, C and Haskell obviously handle it well (they make code optimisations and probably have less function call overhead), while Python does not. So, using psyco was an attempt to make Python code run fast, without changing the complexity of the algorithm, that is, see how much can we speed up an existing Python program without changing its source. Imagine that we were not talking about fibonacci, but about some huge project that ran very slow. Would you really rewrite the whole thing or would you simply add two lines to the source? I hope I made things a little clearer...Filoxhttps://www.blogger.com/profile/07052058313681392060noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-42132358624528097592007-12-12T19:25:00.000-08:002007-12-12T19:25:00.000-08:00I compiled the simplistic version of Fib w/ shedsk...I compiled the simplistic version of Fib w/ shedskin and Time elapsed: 0.782071<BR/><BR/>see my comments @<BR/>http://www.willmcgugan.com/2007/12/12/fun-with-fibonacci/#comments<BR/>and shedskin @ <BR/>http://mark.dufour.googlepages.com/OmahaPythonUsersGrouphttps://www.blogger.com/profile/02566216808097636717noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-36889893136816421832007-12-12T15:04:00.000-08:002007-12-12T15:04:00.000-08:00Okay, I've been out of school for a while, but its...Okay, I've been out of school for a while, but its starting to come back. The problem, I think, is with your algorithm. You are doing a recursive call on yourself twice. I really don't know how Python handles that. If you would refactor that to do a single recursive call, I'm thinking that you will get significant improvements. Unless there is some funny bug for this kind of strange algorithm in Python, I don't think there is any problem with Python's speed. My simple rather standard Pythonesque solution is nothing fancy and it completed the same Fibonacci series in 3 microseconds. You used Psyco and only cut it in half to about 18 seconds! You may as well use a 300 baud modem (yes,I am that old). Even Will using other techniques dramatically and rather impressively improved the run time of that algorithm, but still only got around 3 milliseconds, which is still fairly slow, and it looks like it is slowing down exponentially. You might want to try 300 Fibonacci numbers and see how long that takes. Hey, maybe I'll try that as well. Anybody fressh out school can enlighten us a bit on second order recurrence relations?Bobberinohttps://www.blogger.com/profile/16370024028686171523noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-14846185463223530162007-12-12T11:40:00.000-08:002007-12-12T11:40:00.000-08:00There is something funky about your origianl code....There is something funky about your origianl code. I ran the following in straight Python without Psyco and computed the same sequence in about 4 microseconds. <BR/>import time<BR/><BR/>def fib(n): # write Fibonacci series up to n<BR/> """Print a Fibonacci series up to n."""<BR/> a, b = 0, 1<BR/> while b < n:<BR/> print b<BR/> a, b = b, a+b<BR/><BR/><BR/>startTime = time.clock() <BR/><BR/>fib(10000000)<BR/><BR/>print 'elapsed time: ', (time.clock() - startTime)<BR/><BR/><BR/>But your original code runs in about 45 seconds!! on my machine. That's a 5 order of magnitude difference! I would be interested in finding out why yours takes so long. I haven't had much of a chance to look at it in detail yet, but it computes the first 20 or so values fairly fast, but it then really bogs down. Have you traced the the run time memory or the CPu usage?Bobberinohttps://www.blogger.com/profile/16370024028686171523noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-5705086670510700822007-12-12T08:11:00.000-08:002007-12-12T08:11:00.000-08:00Most of the bloat is Haskell's run time system. It...Most of the bloat is Haskell's run time system. It's a fixed cost, and for a larger executable it won't be nearly so large a code explosion.<BR/><BR/>Kyle.Kylehttps://www.blogger.com/profile/12930542787926104681noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-2280954143476416962007-12-12T04:06:00.000-08:002007-12-12T04:06:00.000-08:00I wrote a faster version, just for the heck of it....I wrote a faster version, just for the heck of it.<BR/><BR/>http://www.willmcgugan.com/2007/12/12/fun-with-fibonacci/Will McGuganhttps://www.blogger.com/profile/14552374744569764596noreply@blogger.com