25 Ağustos 2008 Pazartesi

Case Study Iterative Fibonacci

Wow, it has been long time and i didnt write anything here. That will be a series of articles in which i will be writing some of the algorithms with (mainly) Python. Sometimes i will implement some of them with Java and some of them as Python C extension. I wont use C++ sorry :) I think it is a failure of the object oriented programming but , that is another story. I like the old school C instead of it. In that series i will compare the written algorithms and codes in some areas; how fast they are (O notation and time),how easy was to write them . Any of the comparisons made here are my personal thoughts about that so , i dont claim anything ...

Python :Link
Time :
[makkalot@localhost pyalgorithm]$ time python py_fibo.py 1000000
Result written into fibo.txt

real 3m47.825s
user 3m46.481s
sys 0m0.391s

Level of writing : I think it was quite easy to implement that computation. Additionally i didnt have to think about large numbers python handled all the stuff for me which was cool .

Python Extension :Link

[makkalot@localhost fibo]$ time python ex_fibo.py 1000000
Result written into fibo.txt

real 3m43.437s
user 3m41.899s
sys 0m0.419s

Level of writing : Ah that one was not easy to write :) Firstly i had some difficulties and memory leaks with Py_INCREF and Py_DECREF stuff. The second problem was the big integers thing, so i had to use some Python stuff which made that problem easier.(I wont write that stuff in pure C no no ...) If someone has better solution here please post ...

[makkalot@localhost bin]$ time java sorts.FiboMan 1000000
The fibo result is :written to fib.txt

real 5m31.204s
user 5m18.196s
sys 0m8.927s

Level of writing : Yep that was really easy to write. And also Java has some good solution for these big integers so i only used BigInteger class to handle that situation.But, the code is a little bit longer than Python code.

Concluion : I was really suprised when the pure Python code had almost the best time, so i think i can use the iteratve computations in Python. The dissappointment was the C extension i was expecting some really big difference in time. However the reason seems to be used Python.h functions in C extension. And the Java code really suprised me, its time was really acceptable so people who use Java may write their iterative computational solutions without any concern. That wass my fibonacci iterative test. The second of the series will be the recursive solution for fibonacci and my comments about it ...