CODEWITHSUNDEEP
pythoniterationpermutationambiguous
azuri
azuri

Reputation: 61

Why is one code faster than other even when iterations are more?

My code is short and has lesser number of iterations than the other but still it gets a time limit exceeded error while the other code is accepted on codechef.com. The codes are solution to the "Ambiguous permutation" problem on codechef.com Why is this code:

def inverse(data,x):

    temp=[]

    for i in range(x):
        temp.append(0)
    for i in range(x):
        temp[data[i]-1]=i+1
    return temp

def main():

    while 1:
        x=input()
        if not x:
            return
        data=raw_input().split(' ')
        for i in range(len(data)):
            data[i]=int(data[i])
        temp = inverse(data,x)
        if temp==data:
            print 'ambiguous'
        else:
            print 'not ambiguous'

if __name__ == "__main__":
    main()

faster than this code:

while True:

    output=[]
    n= input()
    if n==0: break
    caseList= raw_input().split()
    amb=1
    for i in range(1, n+1):
        output.append(str(caseList.index(str(i))+1))

    if output==caseList:
        print ("ambiguous")
    else:
        print ("not ambiguous")

Please help me out...

Upvotes: 3

Views: 190

Answers (3)

jsbueno
jsbueno

Reputation: 110311

When such a consistent time difference shows up, we are not talking about something that is 2, or 3 times slower - if one method passes, and the other always times out, it is a huge time difference- normally tied to algorithm complexity.

Although the first code has plenty of room to get better (usage of xrange instead of range, for example), in the final array, the result is update by random access, straight by the index caculated by data[i] - 1- while in the second snippet, you use caseList.index(str(i)) to retrieve each index. The "index" lisr method performs a linear search on the list, starting at the beginning. It may seem little, but when it is doen for each element in the list, your algorithm which was O(N) becomes O(N²) - which expains the dramatic speed down in this second form.

Upvotes: 2

Alexander Corwin
Alexander Corwin

Reputation: 1157

It looks like you're using strings where the other code is using ints, which will slow you down somewhat.

Upvotes: 1

Duncan
Duncan

Reputation: 95682

I take it your second code isn't inside a function.

Access to local variables in a function is significantly faster than accessing global variables. That means code run in global scope is always likely to be slower.

Upvotes: 3

Related Questions