> I wrote the following toy Fibonacci function in Python and
> Java:
>
> [pre]def fib(i):
> if i == 0:
> return 0
> if i == 1:
> return 1
> return fib(i-1) + fib(i-2)
>
> x = 0
> while True:
> print x, fib(x)
> x += 1
>
> At about 35, it's on the order of minutes to complete the
> calculation. With Java, it doesn't slow down to that
> point til about 41 or 42. Since fib(x+1) is more than
> twice as much work as fib(x), that's a pretty big
> difference. (Granted, this is not a very fair test for
> poor Python; it doesn't get to dip into its C libraries,
> and Java doesn't have to do any garbage collection.)
Well, Vladimir already showed a superior solution (more on that, later), but I believe a more throrough excoriation is in order for this flimsy "analysis."
This logic is flawed on so many different levels, that it is difficult to decide where to begin.
First of all, you have fallen into the trap of premature optimization in the extreme. If you are choosing your language/platform based on how well it performs on a single algorithm, that is just utterly ridiculous. Heck, why use anything but assembly?
And again, we are back to the old silly, "Java or Python" instead of the more rational "Java
and Python and..." For the past few months I've been working on a C# project, but at the same time, I use Python for many code-generating and project maintenence and other tasks. Despite its terrible performance on badly written Fibonacci algorithms, it is a great tool that saves me tons of time and makes me much more productive (that it is also fun is just a bonus).
Secondly, if you use just a little common sense on your algorithm and write something like this:
fibs = [0,1,1]
def smartFib(n):
for i in range(len(fibs),n+1):
fibs.append( fibs[-1] + fibs[-2] )
return fibs[n]
You will see that for this particular case, Python is actually quite superior to Java. Because this implementation will quickly take you to Fibonacci numbers that have thousands of digits, you'll have to rewrite your Java solution to use
BigInteger (Python will automatically be using
longs which are arbitrary-length integers). Even after making these adjustments, you'll find that Java craps out because of memory problems long before Python does; I don't know the exact cause, but either the
ArrayList or the
BigIntegers are gobbling too much, or the garbage collector is not giving it back well. The simplicity of the code in this case is particularly dramatic when compared to the (revised) Java code, as well.
In other words, you picked an example which illustrates the opposite of your conclusion.
If your point was to intentionally compare a bad algorithm in the two languages to see which responded better to poorly written code, then that's another thing. I guess the conclusion could be that Java is better at dealing with bad code (maybe that was one of its design criteria; after all, it was heavily marketed and there are likely many more bad Java programmers than bad Python programmers). Anyway, knowing a bit about Python, you wouldn't expect it to excel at recursion, since it is designed to be very flexible and dynamic. If you want some particular algorithm to be highly optimized for performance, then write a C extension, just as you would use JNI to do the same in Java.
On a more realistic note, I have a library of utility functions that I've built up over the years, which includes a GetFileCrc() function. I turned this library into a COM automation server, so that I could use it from JavaScript and subsequently Python (I started the thing before I learned Python and was pleased to learn that Python has very simple access to COM Automation via the Win32 extensions). I was merrily using my COM library to get file CRCs in Python, when I learned that Python's zlib library also had a crc32() function. So, I thought I'd give that a whirl, figuring mine would be much faster, since it does all its work in C. It turns out they are pretty close to equal in performance, even though the data in the zlib case was being read by Python code into manageble chunks (I didn't want read the whole file, because I was working with some that could be several hundred megabytes or more) and sent to the zlib function. The point of this is that you can probably find implementations of common algorithms (CRCs, message digests, encryption, compression, etc.) in Python that have excellent performance (often implemented in C as extensions), so this argument that Python needs to be fast at low-level algorithms (well-written or otherwise) is completely specious.
By the way, as a rule of thumb, if you can write out the results of a calculation faster with a pencil and paper than your algorithm can do on a modern CPU in any programming language, something is wrong. I'm not kidding: try doing the first 50 Fibonacci numbers by hand -- it should take less than 5 minutes, even if you check your numbers.