How come these Python codes perform so much differently

Question

Please look at the following code to solve the same set of problem, I do not think that mentioning the problem would anyhow help the purpose, it's yet another iteration of the Josephus problem:

Solution 1:

import sys
from math import log

cases= int(sys.stdin.readline())
current= 0
while current < cases:
    current += 1
    n = int(sys.stdin.readline())
    print 2*(n - 2**(int(log(n,2))))+1

This solution solves the given 10 test cases in cumulative 1.0912 seconds and consumes 4360KiB of memory.

Solution 2:

def josephus_2( n ):
    from math import log
    return 2*(n - 2**(int(log(n,2))))+1

import sys
cases= int(sys.stdin.readline())
current= 0
while current < cases:
    current += 1
    n = int(sys.stdin.readline())
    print josephus_2( n )

this solution solves the same 10 test cases in a total of 1.0497 seconds and 640KiB of memory.

Being a Python n00b I was wondering, while according to the online judge I earn same points for both, but what makes the solution 2 more faster than 1 and much more memory efficient? I know that the time difference can sound very less, but at the same time ranks me first on the fastest solution, even faster than c/c++/perl submissions

Can this Screenshot help?

Is there any way you can test this yourself? The first way is much faster for me. — Blender, Mar 08 '13 at 04:20
It might be something to do with the JITing being easier if the complex function is separated into its own method. Just a guess — Patashu, Mar 08 '13 at 04:22
Have you tried decompiling it with [dis](http://docs.python.org/2/library/dis.html)? — gberger, Mar 08 '13 at 04:25
@wrongnumber wrap each solution into a function, and then call dis.dis(the_function) for each — gberger, Mar 08 '13 at 04:37
Check this http://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function The byte code generated differs because of variable scope i.e. local vs global — Ankit Jaiswal, Mar 08 '13 at 05:20

Developer · Answer 1 · 2013-03-08T05:45:29.367

1

In my old experiences I remember that I had found that putting computation parts in a function (method) sometime may improve the performance:
I just re-experienced using the following simple code:

n = 1000000
def compute(n):
    j = 0
    for i in xrange(n):
        j += 1

tic()
compute(n)
toc()

>>> 0.271 s

tic()
j = 0
for i in xrange(n):
    j += 1
toc()

>>> 0.849 s

The result shows 0.271s for the first (using compute) vs 0.849s as inline code. This is noticeable improvement without changing anything in the main computation part! So the point is using a method may improve the performance.

Here are the code you may use for performance comparison:

from __future__ import division
from time import clock

def compute(n):
    j = 0
    for i in xrange(n):
        j += 1

n = 1000000
print 'solution (2) using a method call...'
t0 = clock()
compute(n)
print clock()-t0
#>>> ~0.2415...                              #faster (solution 2)

print 'solution (1) all inline code...'
t0 = clock()
j = 0
for i in xrange(n):
    j += 1
print clock()-t0
#>>> ~0.6169...                              #slower (solution 1)

edited Mar 08 '13 at 05:45

answered Mar 08 '13 at 04:50

Developer

8,258
8
49
58

I think in my case it is the other way round... :) – whizzzkid Mar 08 '13 at 05:04
@whizzzkid But in your question, first solution (without method) took 1.0912 s while the second solution which uses a method took only 1.0497 s. This means using a method improved in your case saving 0.0415 s. So as explained in my answer using method improves the performance. Don't miss up that in my answer the first is using a method (i.e., your second solution). – Developer Mar 08 '13 at 05:21
I just tried your code using [`timeit`](http://docs.python.org/2/library/timeit.html) and got identical results for both methods (using the `min` of the `repeat` method with `repeat=7, number=10` and appropriate `stmt` and `setup` strings). – Wesley Baugh Mar 08 '13 at 05:23
@WesleyBaugh you may be right if using timeit (!?), but if you try the timing approach given above you will see noticeable improvement as explained. – Developer Mar 08 '13 at 05:47

How come these Python codes perform so much differently

1 Answers1