3

私のコードは短く、他のコードよりも反復回数が少ないですが、他のコードが 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")

私を助けてください...

4

3 に答える 3

3

あなたの 2 番目のコードは関数内にないと思います。

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

于 2012-03-01T20:32:04.887 に答える
2

このような一貫した時間差が現れる場合、2倍または3倍遅いものについて話しているわけではありません。一方の方法が合格し、もう一方の方法が常にタイムアウトする場合、それは大きな時間差であり、通常はアルゴリズムの複雑さに関係しています。

最初のコードには改善の余地が十分にありますが（たとえば、範囲の代わりにxrangeを使用）、最終的な配列では、結果はランダムアクセスによって更新され、data[i] - 1-によって計算されたインデックスによって直接更新されます。2番目のスニペットでは、caseList.index(str(i))各インデックスを取得するために使用します。「index」lisrメソッドは、リストの最初から線形検索を実行します。少し見えるかもしれませんが、リスト内の各要素に対して実行すると、O（N）であったアルゴリズムはO（N²）になります。これは、この2番目の形式で劇的な速度低下を示します。

于 2012-03-02T05:19:57.180 に答える
1

他のコードが int を使用している場所で文字列を使用しているようです。これにより、速度が多少低下します。

于 2012-03-01T20:37:38.533 に答える