Why is this Python code faster than its equivalent Clojure code

user_5848607 0
Viewed 326

I've been told, and I believe, that Clojure is faster than Python. Why does this Python code run faster than this seemingly equivalent Clojure code? Is Python doing some optimizations at compile time?

def find_fifty(n,memory=1,count=0):
    if memory < 0.5:
        return count
    else:
        return find_fifty(n,memory*(1 - count/n),count+1)

find_fifty(100000) 

(defn fifty 
    ([n] (fifty n 1 0))
    ([n memory count]
        (if (< memory 0.5)
            count
            (recur n
                   (* memory (- 1 (/ count n)))
                   (inc count)))))

(fifty 100000)

It feels like the time complexity for Clojure is higher than for Python. The Python function can receive an input many times higher than the Clojure function before it has a significant increase in runtime.

Update - Clojure Fix

(defn fifty 
    ([n] (fifty (float n) 1 0))
    ([n memory count]
        (if (< memory 0.5)
            count
            (recur n
                   (* memory (- 1 (/ count n)))
                   (inc count)))))

(fifty 10000000)

As was answered, Clojure was keeping values as very large rational numbers. Converting it to a float simplifies the operations being done, thus decreasing the runtime.

runtime clojure optimization python
2 Answers

Clojure's division operator, when applied to integers, does exact rational division. It does not round down to the next lowest integer as Python's does. Your algorithm involves memory becoming a very complex fraction, despite yielding a simple integer.

I've amended your function to print its intermediate values before finally returning the result:

(defn fifty
  ([n] (fifty n 1 0))
  ([n memory count]
    (if (< memory 0.5) 
      count 
      (do (println n (* memory (- 1 (/ count n))) (inc count)) 
          (fifty n (* memory (- 1 (/ count n))) (inc count))))))

And here is the outcome:

(fifty 500)
500 1 1
500 499/500 2
500 124251/125000 3
500 61752747/62500000 4
500 1914335157/1953125000 5
500 189519180543/195312500000 6
500 46811237594121/48828125000000 7
500 23077940133901653/24414062500000000 8
500 2838586636469903319/3051757812500000000 9
500 1393746038506722529629/1525878906250000000000 10
500 68293555886829403951821/76293945312500000000000 11
500 33395548828659578532440469/38146972656250000000000000 12
500 2037128478548234290478868609/2384185791015625000000000000 13
500 992081569052990099463209012583/1192092895507812500000000000000 14
500 241075821279876594169559790057669/298023223876953125000000000000000 15
500 23384354664148029634447299635593893/29802322387695312500000000000000000 16
500 2829506914361911585768123255906861053/3725290298461914062500000000000000000 17
500 1366651839636803295926003532603013888599/1862645149230957031250000000000000000000 18
500 329363093352469594318166851357326347152359/465661287307739257812500000000000000000000 19
500 158423647902537874867038255502873972980284679/232830643653869628906250000000000000000000000 20
500 475270943707613624601114766508621918940854037/727595761418342590332031250000000000000000000 21
500 227654782035946926183933973157629899172669083723/363797880709171295166015625000000000000000000000 22
500 54409492906591315357960219584673545902267911009797/90949470177292823791503906250000000000000000000000 23
500 25953328116444057425747024741889281395381793551673169/45474735088646411895751953125000000000000000000000000 24
500 3088446045856842833663895944284824486050433432649107111/5684341886080801486968994140625000000000000000000000000 25
500 58680474871280013839614022941411665234958235220333035109/113686837721616029739379882812500000000000000000000000000 26
500 13907272544493363279988523437114564660685101747218929320833/28421709430404007434844970703125000000000000000000000000000 27
27

I hope you can see how expensive it would be to compute these unreasonable fractions for even small inputs. If you want the same logic as the Python version, you could simply replace / with quot.

user_6254030

A couple of suggestions:

The n argument to the function fifty, either OP's or @amalloy's, is not changed by the recur. So better do it with a loop:

(defn fifty [n]
  (loop [memory 1.0, count 0]
    (if (< memory 0.5)
      count
      (recur (* memory (- 1 (/ count n))) (inc count)))))

By setting the initial value of memory to 1.0 instead of 1, the * produces a series of floats (doubles, to be exact), not rationals.

We could use sequence functions to make what's going on clearer:

(defn fifty- [n]
  (let [factors (map (fn [count] (- 1 (/ count n))) (range))
        products (reductions * 1.0 factors)]
    (count (take-while #(< 0.5 %) products))))

This is probably the slowest of the lot.

user_15623150
Related