Re:Introducing Surinx (Ruby syntax w/ Java typing)
by lliiffee on Wednesday August 26, 2009 @11:30AM
(#787339)
I just tried it with psyco. I get about 103 seconds with normal python and about 4 seconds with psyco. (Including the imports.)
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by ginkgo on Wednesday August 26, 2009 @11:24AM
(#787317)
Or you could simply make your python code tail-recursive:
$ time python fib.py 40
102334155
real 0m0.013s
user 0m0.000s
sys 0m0.010s
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by carbon8 on Wednesday August 26, 2009 @12:03PM
(#787412)
Then you are testing two different things, and if you use tail recursion even Ruby 1.9 still runs it faster than Python.
# 400
$ time ruby fib.rb
real 0m0.017s
user 0m0.010s
sys 0m0.006s
# 400
$ time python fib.py
real 0m0.023s
user 0m0.011s
sys 0m0.011s
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by apgwoz on Wednesday August 26, 2009 @12:27PM
(#787474)
Of course you can, but that's not going to work when you run out of stack space. The point of my stupid benchmark was to write the equivalent ruby code, and then the equivalent C code, forgetting the fact that there's a much more optimal way to do it (e.g. write it in scheme with tail calls).
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by apgwoz on Wednesday August 26, 2009 @06:18PM
(#788195)
> was to write the equivalent ruby code,
that should have stated "equivalent python code"
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by steveklabnik on Wednesday August 26, 2009 @12:31PM
(#787486)
Python does not do tail call optimization.
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by gloob on Wednesday August 26, 2009 @01:30PM
(#787627)
Whether it does tail call optimization is a different question than whether you can write the algorithm in a tail-recursive manner, though.
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by steveklabnik on Wednesday August 26, 2009 @01:33PM
(#787637)
Yes, but without the optimization, how would it help? Am I just being a n00b?
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by mbrubeck on Wednesday August 26, 2009 @02:24PM
(#787745)
Writing it tail-recursively forces you to switch from the O(2^n) algorithm (which has two recursive calls; you can't put both into tail position) to a more efficient algorithm. You could also write the more-efficient algorithm without tail recursion, of course.
Re:Introducing Surinx (Ruby syntax w/ Java typing)
by apgwoz on Wednesday August 26, 2009 @02:19PM
(#787735)
No, you're not being a n00b. It'll help because the stack usage will grow linearly as opposed to quadratically, as in the case of the naive solution. You'll still overflow the stack without the optimization.
I just rewrote it in C though:
Which makes the python version something like 35x slower in wall clock time.