4 ms·

Does fib.py use psyco? If not, that does still seem slow. Standard numerical benchmarks indicate that c or fortran or whatever should have a much larger speed

Does fib.py use psyco? If not, that does still seem slow. Standard numerical benchmarks indicate that c or fortran or whatever should have a much larger speed advantage relative to regular python than 40/163. E.g. on the n-body benchmark here: http://shootout.alioth.debian.org/u32/benchmark.php?test=nbody&lang=all http://shootout.alioth.debian.org/u32/benchmark.php?test=nbo... Python is about 65 times slower than c/c++/java/fortran/scala.

apgwoz 17y ago
No, it doesn't use psyco. If it did, I'd expect it to be faster of course. I just rewrote it in C though: $ time ./fib 40 102334155 real 0m3.063s user 0m2.912s sys 0m0.014s Which makes the python version something like 35x slower in wall clock time.
- ginkgo 17y ago
  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
  - carbon8 17y ago
    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
  - apgwoz 17y ago
    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).
    - apgwoz 17y ago
      > was to write the equivalent ruby code, that should have stated "equivalent python code"
  - steveklabnik 17y ago
    Python does not do tail call optimization.
    - gloob 17y ago
      Whether it does tail call optimization is a different question than whether you can write the algorithm in a tail-recursive manner, though.
      - steveklabnik 17y ago
        Yes, but without the optimization, how would it help? Am I just being a n00b?
        apgwoz 17y ago
        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.
        mbrubeck 17y ago
        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.
- lliiffee 17y ago
  I just tried it with psyco. I get about 103 seconds with normal python and about 4 seconds with psyco. (Including the imports.)

apgwoz 17y ago

No, it doesn't use psyco. If it did, I'd expect it to be faster of course. I just rewrote it in C though: $ time ./fib 40 102334155 real 0m3.063s user 0m2.912s sys 0m0.014s Which makes the python version something like 35x slower in wall clock time.

ginkgo 17y ago
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
- carbon8 17y ago
  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
- apgwoz 17y ago
  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).
  - apgwoz 17y ago
    > was to write the equivalent ruby code, that should have stated "equivalent python code"
- steveklabnik 17y ago
  Python does not do tail call optimization.
  - gloob 17y ago
    Whether it does tail call optimization is a different question than whether you can write the algorithm in a tail-recursive manner, though.
    - steveklabnik 17y ago
      Yes, but without the optimization, how would it help? Am I just being a n00b?
      - apgwoz 17y ago
        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.
      - mbrubeck 17y ago
        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.
lliiffee 17y ago
I just tried it with psyco. I get about 103 seconds with normal python and about 4 seconds with psyco. (Including the imports.)