反復回数が多い場合でも、1つのコードが他のコードより高速なのはなぜですか？

Question

私のコードは短く、他のコードよりも反復回数が少ないですが、codechef.comで他のコードが受け入れられている間も、時間制限を超えてエラーが発生します。コードはcodechef.com の「あいまいな順列」の問題を解決しているのはなぜこのコードは次のとおりです。

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() 

このコードよりも速く

：

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")  

...

Answer 1

このような一貫した時間差が現れた場合、我々は2倍または3倍の遅れについて話しているわけではありません - 1つのメソッドが通過し、もう1つが常にタイムアウトすると、アルゴリズムの複雑さ。

最終的な配列では、最初のコードは十分な余裕があります（例えば、範囲の代わりにxrangeを使用します）。結果はdata[i] - 1のインデックスでまっすぐにランダムアクセスで更新されます。 2番目のスニペットでは、caseList.index(str(i))を使用して各インデックスを取得します。 "index" lisrメソッドは、最初からリストの線形検索を実行します。それはほとんど見えないかもしれませんが、リスト内の各要素についてdoenであるとき、O（N）であったアルゴリズムはO（N²）になります - この第2の形式では劇的なスピードが減ります。

Answer 2

を私を助けてください。

私はそれをあなたの2番目のコードは、関数内ではありませんそれを取る。

関数内のローカル変数へのアクセスは、グローバル変数へのアクセスよりもはるかに高速です。つまり、グローバルスコープで実行されるコードは常に遅くなる可能性があります。

Answer 3

他のコードがintを使用しているところで文字列を使用しているようですが、いくらか遅くなります。